Resetting ssh server host key

Today I tried logging on to a server that was recently down due to a brute force attack. Using the SSH command resulted in the following warning:

@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@
@ WARNING: REMOTE HOST IDENTIFICATION HAS CHANGED! @
@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@
IT IS POSSIBLE THAT SOMEONE IS DOING SOMETHING NASTY!
Someone could be eavesdropping on you right now (man-in-the-middle attack)!
It is also possible that the RSA host key has just been changed.
[...]

In this case, the problem was that the RSA host key had changed. After searching the net for a while, I found that some people routinely delete their known_hosts file because of this. However, there is a proper solution to the problem, as presemted by *ccm* in this blog post:

ssh-keygen -R

where is replaced with the name of the server that you're trying to connect to.