1. Upload your new SSH Key, or use one made by AWS
2. Make an AMI of your instance
3. Launch a new machine from your AMI, select the new SSH Key
4. Log in your machine with default user (ubuntu, ec2-user, depends on your original AMI image)
5. Change the Elastic IP to the new machine
6. Turn of the old machine and terminate it.