A chave SSH enviada para o servidor remoto é a chave pública , que é uma das duas partes da "chave SSH" real. Ele foi projetado para ser 'publicamente' divulgado para servidores remotos, já que você precisa da chave privada correspondente, que é armazenada no seu computador para funcionar com a conexão. (Um exemplo análogo é a criptografia PGP que funciona de maneira semelhante - a chave pública PGP pode ser usada para criptografar dados, mas a chave privada PGP é necessária para descriptografar as informações e usá-las. Da mesma forma, o SSH precisa que você tenha a chave privada que corresponde à chave pública para fazer autenticação baseada em chave.)
Se você formatou seu sistema, perdeu sua chave privada e gravou dados no disco desde então, provavelmente não é possível recuperar a chave privada SSH.
Verifique com o provedor do servidor remoto e veja se eles têm um console serial para acessar o sistema. Se é um VPS, eles provavelmente têm esse mecanismo disponível através de um painel de controle. Crie uma nova chave SSH em seu computador, carregue a chave privada no servidor através do console serial, remova a chave privada antiga e conecte-se normalmente.