ssh remote host identification has changed

I've reinstalled my server and I am getting these messages:

[user@hostname ~]$ ssh root@pong
@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@
@    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 a host key has just been changed.
The fingerprint for the RSA key sent by the remote host is
6e:45:f9:a8:af:38:3d:a1:a5:c7:76:1d:02:f8:77:00.
Please contact your system administrator.
Add correct host key in /home/hostname /.ssh/known_hosts to get rid of this message.
Offending RSA key in /var/lib/sss/pubconf/known_hosts:4
RSA host key for pong has changed and you have requested strict checking.
Host key verification failed.

I have tried various solutions that I found on the Internet. My known_hosts file (normally in ~/.ssh/known_hosts) is in /var/lib/sss/pubconf/known_hosts. I've tried to edit it, but it remains in one state. I have installed ipa-client and have Fedora 19. How do I resolve this warning?

All the answers answered so far work only if you do not have Freeipa installed.

The right answer for freeipa in comments below from adrin is here.

Here is the simplest solution

ssh-keygen -R <host>

For example,

ssh-keygen -R 192.168.3.10

From ssh-keygen man page:

• -R hostname Removes all keys belonging to hostname from a known_hosts file. This option is useful to delete hashed hosts (see the -H option above).

Use

ssh-keygen -R [hostname]

Example with an ip address/hostname would be:

ssh-keygen -R 168.9.9.2

This will update the offending of your host from the known_hosts. You can also provide the path of the known_hosts with -f flag.

I had this same error occur after I recreated a Digital Ocean Ubuntu image. I used the following command with my server IP in place of [IP_ADDRESS]

ssh-keygen -R [IP_ADDRESS]

The sledgehammer is to remove every known host in one fell swoop:

rm ~/.ssh/known_hosts

I come up against this as we use small subnets of short-lived servers from a jump box, and frequently have internal IP address reuse of servers that share the same ssh key.