Se você não tiver a chave de correspondência correta para uma instância, o servidor não o deixará entrar. As chaves registradas no EC2 só serão configuradas em uma imagem durante a inicialização, portanto, você não poderá alterá-la enquanto a máquina está online.
Se você tiver um volume do EBS, poderá reconectá-lo como um volume secundário de uma nova instância, corrigir seu erro carregando a nova chave nele e, em seguida, anexá-lo de volta à instância antiga. Caso contrário, você perdeu seu servidor.