To replace the key pair of a running instance, the following steps must be followed :
1) Go to AWS Console and create a new key pair
2) Generate a public key from the recently generated private key
3) Copy the generated public key into ~/ssh/authorized_keys of server
4) Delete the previous key from ~/ssh/authorized_keys of server
5) SSH into the instance using the new key
Hope this works!
In case, there is still some confusion, refer to this video on creating EC2 instances :