Recovering an EC2 Instance After Losing Private Key

This is not supported by the AWS web console or API. To fix this, you'll have to create a rescue instance, mount the volume as a secondary volume in the rescue instance, and then go in and edit the public key in /<mountpoint>/home/ec2-user/.ssh/authorized_keys, changing it to a new key you have created.