1. Если бы ключ _изменился_, соединиться вообще не получилось бы, потому что ssh не позволит. у топикстартера соединение не запрещщается, значит у него тупо динамический IP (решение выше, но это небезопасно!)
2. весь файл ~/.ssh/known_keys удалять нельзя. Ругаясь на измменившийся ключ, ssh пишет старый ключ, новый ключ и номер строчки в файле, в которой сохранён старый ключ. Если уверен, что ломишься на правильную машину, и знаешь, почему сменился ключ - удали только одну строчку!