Check out this official documentation for a detailed version - https://docs.aws.amazon.com/AWSEC2/latest/UserGuide/ec2-key-pairs.html#replacing-lost-key-pair
Or Follow these steps:
1. Stop the running EC2 instance
2. Detach /dev/xvda1 volume (let's call it volume1)
3. Start a new t1.micro EC2 instance, using your new key pair. Create it in the same subnet, if not you’ll have to terminate the instance and create it again.
4. Attach volume1 to the newly created micro instance, as /dev/xvdf (or /dev/sdf)
5. SSH to the new micro instance and mount volume1 to /mnt/tmp
$ sudo mount /dev/xvdf1 /mnt/tmp
6. Copy ~/.ssh/authorized_keys to /mnt/tmp/home/ubuntu/.ssh/your_keys
7. Logout
8. Terminate micro instance
9. Detach volume1 from it
10. Attach volume1 back to the main instance as /dev/xvda
11. Start the main instance
12. Login as before, using your new .pem file