I will leave the sed solution for the real gurus. As far as I am concerned the easy way to get the job down is use the ssh-keygen -R your_host command.
If you are working in a environment with a DNS suffix, then you will probably need a second invocation like: ssh-keygen -R your_host.your_domain.
