I use a notebook with Ubuntu 12.10 and try to connect a server with Ubuntu 12.04. The server has already installed openssh-server. And allow publick key and password to login. But I connect the server sometime well but after minutes it will be error. First, it will show me these messages:

   WARNING: REMOTE HOST IDENTIFICATION HAS CHANGED!
   ......
   Add correct host key in /home/myname/.ssh/known_hosts to get rid of this message.

but I never reinstall system and the openssh-server. Both are never changed! The server nerver shutdown or reboot.

Second, after I remove the relative key from my known_hosts and use ssh connect the server again, it will let me type my password. then my nightmare coming... Permission denied (publickey,password)

But I typed the correct password!

PS: I used password and public key both success. But the problem will appear again after i logout then login.