Sim, geralmente é tão simples quanto as duas etapas mencionadas.
Se você adicionou sua chave a ~/.ssh/config para escolher automaticamente a chave certa para usar com o host certo com uma diretiva IdentityFile , talvez também queira removê-las de lá.
Você também pode querer remover, na (s) sua (s) máquina (s) cliente ssh, as linhas em ~/.ssh/known_hosts que se referem ao (s) servidor (es) ssh ao qual você se conectou, para que o cliente também se esqueça do servidor .