Se você não consegue inicializar em um shell de root, você está meio desossado. Eu já vi isso acontecer antes, quando as pessoas esquecem de alterar o acesso no arquivo de chave. O método recomendado é tentar usar a chave antes para desativar a autenticação baseada em senha.
Se for uma instância em uma nuvem, ligue para seu provedor e solicite a redefinição da senha (que pode não ser gratuita ou mesmo oferecida).
Se for uma caixa real e você tiver alguém por perto, chame-a e suborne-a com pizza.
Caso contrário, precisa entrar no seu carro.
Quando você chegar ao computador, pressione qualquer tecla F mágica para acessar o menu de inicialização e selecione "root shell". Monte o sistema de arquivos como gravável. Em seguida, edite o arquivo de configuração de volta para onde começou e tente novamente.
Além disso, normalmente faço isso enquanto estou sentado em frente à caixa, exatamente por isso. Em um caso de VPS, pratico o método em uma caixa local primeiro para ter certeza de que estou certo.