You could try regenerating all of your server keys (it can't hurt, unless you have clients that expect the old keys):
ssh-keygen -t rsa1 -f /etc/ssh/ssh_host_key -N ''
ssh-keygen -t rsa -f /etc/ssh/ssh_host_rsa_key -N ''
ssh-keygen -t dsa -f /etc/ssh/ssh_host_dsa_key -N ''
Note that '' is two single quotes, not a double quote.
The error about looking for RSA1 keys in the RSA and DSA files seems strange though. If regenerating keys doesn't work you should post your sshd_config.
Luego
/etc/init.d/ssh restart.