Thanks for the tips guys. Will definitely keep them in mind when I need to rest the key pairs.
However, in the interest of efficiency and laziness I've come up with something else:
- Create your new key pair and download the credentials
- Right-click your instance > Create AMI Once it is done
- terminate your instance (or just stop it until you are sure you can create another one from your new shiny AMI)
- Start a new EC2 instance from the AMI you just created and specify your new key pair created in step (1) above.
Hope this can be of use to you and save you some time as well as minimize the amount of white hair you get from stuff like this :)