Só é possível recuperar o acesso a uma instância Linux com suporte do EBS.
Mas, para instâncias regulares, não é possível recuperar a chave, pois a AWS não salva uma cópia dela.
Portanto, no seu caso, se suas instâncias não forem respaldadas pelo EBS, você terá que destruir as instâncias, criar uma nova chave e novas instâncias usando a nova chave.
Mais informações podem ser encontradas aqui .
Esta é a informação relevante do link acima:
Amazon EC2 doesn't keep a copy of your private key; therefore, if you lose a private key, there is no way to recover it. If you lose the private key for an instance store-backed instance, you can't access the instance; you should terminate the instance and launch another instance using a new key pair. If you lose the private key for an EBS-backed Linux instance, you can regain access to your instance. For more information, see Connecting to Your Linux Instance if You Lose Your Private Key.
Editar # 1:
Para recuperar o acesso às instâncias apoiadas por ebs, você deve parar a instância, desconectar seu volume raiz e anexá-lo a outra instância como volume de dados, modificar o arquivo authorized_keys para adicionar sua chave ssh recém-criada, mover o Volte para a instância original e reinicie a instância.
Informações sobre esse processo podem ser encontradas aqui .