Se o servidor tiver backup EBS, você poderá pará-lo e montar seu volume raiz como um sistema de arquivos em uma instância AWS diferente no mesmo AZ ao qual você tem acesso root e usar essa instância para editar as chaves ssh. Se você precisar de instruções mais detalhadas do que isso, precisará pagar a alguém com uma experiência decente de sysadmin e AWS para fazer isso por você.
Se o servidor for armazenamento de instâncias, você precisará criar um tíquete de suporte com o suporte da AWS. Eu não sei como entrar em uma instância de loja de instância na situação descrita por você. Se forem apenas os dados necessários e os dados em um volume do EBS, você poderá montar esse volume em uma instância diferente, conforme descrito acima.