Você precisará excluir o conteúdo do diretório host remoto ou ele não reconhecerá a nova chave e chmod 700 (não 600) ambos os diretórios .ssh (host local e remoto).
Após gerar o novo par de chaves, insira o comando no host local cat .ssh/id_rsa.pub | ssh <user>@<remotehost> 'cat >> .ssh/authorized_keys'
Isso levará a saída de suas chaves autorizadas em sua máquina local e a colocará também na máquina remota. Além disso, você precisará garantir o acesso RWX, e não apenas o RW.