Before starting, save on your instance the key-first-one.pem ( orginal pem file which you get it at configure of the instance first time )
1. From the AWS EC2 Console -> Key Pairs and generate a new key pair (eg: keynew.pem);
Download the generated pem key, and chmod it to 0666
2. Use the new pem key to generate a public key
$ ssh-keygen -y
When prompted, enter the path to keynew.pem ( /path/to/keynew.pem ) . This will generate on console not in file
Touch keynew.pub and paste his content form generated process.
Tip: Edit keynew.pub and append the key's name so you can identify it easier in the next steps.
Just append a single space, then a tag/name for the key
3. Add the new public key to your instance
$ cat /path/to/keynew.pub | ssh -i /path/to/key-firstone.pem user@ip-private-from-aws "cat >> .ssh/authorized_keys"
4. Test the new key by logging in and removing the old/original key
$ ssh -i /path/to/keynew.pem user@ip-private-from-aws
$ nano ~/.ssh/authorized_keys
Find the line containing the "original name" key and remove it.