В последних версиях openssh (столкнулся на свежеустановленной ubuntu) включен по умолчанию параметр конфигурации HashKnownHosts, в результате в .ssh/known_hosts сохраняются хосты в виде хеша, и при необходимости удалить оттуда запись старый метод с использованием любого редактора для удаления текстовой строки перестал быть актуальным. Гугление подсказывает как с этим работать:
Ищем наш хост

ssh-keygen -H  -F hostname

и удаляем его при необходимости

ssh-keygen -R hostname