problema con Shh / Sshd

[David Aravena A.]

Hola lista,

Al  conectar via ssh a una máquina "X" de la red me aparece el siguiente 
mensaje:
    
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.
The fingerprint for the RSA key sent by the remote host is
72:f0:1d:8b:44:2a:c4:d4:3e:4b:f7:ea:ec:bb:c1:fc.
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
RSA host key for 192.168.5.22 has changed and you have requested strict 
checking.
Host key verification failed.

Pero al intentar una conexion desde la máquina X hacia la mía no hay problema, 
ya verifique los servicios sshd y están corriendo bien, tb verifique las 
llaves pero aun así no funca ¿alguien ha tenido problema similar?

Algradezco comentarios, experiencias etc.

pd: tengo en mi poder los respectivo howto y man del servicio y creo estar 
siguiendo todo al pie de la letra.

Atte David Aravena A.