How To Replace a lost Key Pair with new one on an EC2 instance

Access to Amazon EC2 instances specially the Linux instances are always protected by a private key pair. Private key is only the way to get access to the instance, what if you lost the key? Is your servers lost in black hole? Thankfully nothing is lo...