Se nada mais funcionar, o que você poderia fazer é criar uma imagem da AMI a partir da sua instância atual e, em seguida, iniciar uma nova instância dessa AMI. Ao iniciar a nova instância, você terá a opção de criar uma nova chave privada ou usar uma existente. Se você puder conectar-se à nova instância, apenas termine o antigo e atribua o Elastic IP ao novo.
Editar : Se você ainda não conseguir se conectar à nova instância, você pode disparar uma nova instância (usando uma vanilla Ubuntu AMI, não a sua) e depois montar o volume do EBS instância para a nova instância. Isso permitiria que você tivesse acesso ao sistema de arquivos da instância quebrada e talvez encontrasse uma maneira de consertá-lo ou, pelo menos, copiar arquivos dele. As etapas detalhadas estão descritas em esta postagem .