[dscrd]

... and then you do rm .ssh/known_hosts and try again :P

[lorenzhs]

ssh-keygen -f ~/.ssh/known_hosts -R 123.45.67.89

[erpellan]

If you get past the terrifying warning, it even gives you the command to copy and paste. You don't even have to type it!

[corobo]

You have probably just saved me.. minutes of time over the course of a year!

But seriously thanks, I was going into the known_hosts file and manually deleting the offending line :)