This hasn’t happened to me, but knowing that it could encourages me to take note of how to address the scenario if it occurs. I came across a great example here (great step-by-step instructions).
To sum up:
- Shutdown your instance
- Create an AMI
- Launch an instance from an AMI where you can create/choose a private key
- Re-associate an EIPs
- Terminate the old instance
Such a convenient approach to what could otherwise be a very frustrating situation. I’ll be following kirillplatonov.com for more useful tips!