Bueno, en realidad es justamente eso, agregar la llave, pero creo que no es lo más cómodo. Hay una solución que creo que es mucho más segura, si lo que quieres es simplemente solucionar el problema de que no te deja acceder por ssh.
Se trata de borrar las anteriores llaves que tenías en tu archivo de hosts conocidos ~/.ssh/known_hosts
Sería simplemente este comando:
ssh-keygen -R -AQUÍ_PONES_LA_IP_DEL_SERVIDOR-
Con ese comando se modificará el archivo known_hosts sin que tengas que editarlo a mano ni nada. Luego te dejará acceder por ssh.