Sometimes host key verification fails because the host was replaced, IP has changed or something like this (also it could be a man in the middle attack).
In my case I work with high availability clusters and we often have the case that there is switch of the host. To avoid manual editing of the .ssh/known_hosts file I have written a simple bashrc alias / function.
#simple function to remove a line from .ssh/known_hosts cleanup_known_hosts(){ if [ x$1 == x ]; then echo "Syntax : cleanup_known_hosts Linenumber" else \cp ~/.ssh/known_hosts ~/.ssh/known_hosts_backup.$$ sed $1'd' ~/.ssh/known_hosts > /tmp/known_hosts_temp.$$ && \cp /tmp/known_hosts_temp.$$ ~/.ssh/known_hosts rm -f /tmp/known_hosts_temp.$$ echo "Finished" fi } alias cleanup_known_hosts=cleanup_known_hosts
With small adoptions you can use this function for all situations where you have to remove a given line in a file.