Host key verification failed!

Usually I pass on the firewall to log-in in my server Behind it. I Reinstall existing server to a new linux flavor and my firewall ask me this..

# ssh 1xx.x1.x4.x5 -l root
@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@
@ 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 DSA host key has just been changed.
The fingerprint for the DSA key sent by the remote host is
f0:12:cf:37:98:0a:05:f1:44:cr:3b:6b:59:39:5d:e6.
Please contact your system administrator.
Add correct host key in /root/.ssh/known_hosts to get rid of this message.
Offending key in /root/.ssh/known_hosts:1
DSA host key for 1xx.x1.x4.x5 has changed and you have requested strict checking .
Host key verification failed.

then i need to remove this so my firewall got the new host key...

#rm -fr /root/.ssh/known_hosts

# ssh 1xx.x1.x4.x5
The authenticity of host '1xx.x1.x4.x5 (1xx.x1.x4.x5)' can't be established.
DSA key fingerprint is f0:12:cf:37:98:0a:05:f1:44:cr:3b:6b:59:39:5d:e6.
Are you sure you want to continue connecting (yes/no)? yes
Warning: Permanently added '1xx.x1.x4.x5' (DSA) to the list of known hosts.
root@1xx.x1.x4.x5 's password:
Last login: Sun Oct 24 04:42:06 2010 from 11xx.x1.x4.x5
#

I'M IN