1. Create a new key pair in PuTTY Key Generator:

2. Open the Amazon EC2 console.

3. Select your EC2 instance and stop it.

4. Select your EC2 instance -> Actions -> Edit user data

5. Copy the following script into the Edit user data dialog box:

Content-Type: multipart/mixed; boundary="//"
MIME-Version: 1.0

--//
Content-Type: text/cloud-config; charset="us-ascii"
MIME-Version: 1.0
Content-Transfer-Encoding: 7bit
Content-Disposition: attachment; filename="cloud-config.txt"

#cloud-config
cloud_final_modules:
- [users-groups, once]
users:
- name: centos
ssh-authorized-keys:
- ssh-rsa AAAAB3NzaC1yc2EAAAABJQAAAQEA2sX2aEgRLosg/4a9PTevKMHVhTCByVQt+MN/USKoPOXCkCrWYagVucuRkl3uzJz/+v7W0y7rkFaA8vEqruXwv+O3/aXstg7hUimRHZ9tyA1zUp3/nXBMXnSCd8vrnba272XXVeaDA3eIKpL8W+WHWiE6hEbjg06uv0x7mDTR5ygK+GV67VD+YJLniOVeEvlqaFuDaNcVW2wFuy31TVZKShfqyQW5imW8nkeS6txl1SxdQ6fU1n0rpZAkAp6m8TKfip2btK/fZqqzRCjWGdO7w8dHS1cHrdUYEHxKxbu24u0172NnCD7CIVYOJ8FV41MmN1pLfHp+fWJi1XXHLJXOow== new-ec2-key

Important: You have to replace ssh-rsa... on yours key!

6. Save changes.

7. Start your EC2 instance.

8. Validate a new public key.

9. Stop your EC2 instance and delete all the text in Edit user data dialog box!

10. Start your instance!