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