When the SSH Server use both RSA and DSA, actually (by default) the OpenSSH client is obliged to know the RSA public key of the server. If we change the preference key to use in the ssh_config with the option HostKeyAlgorithms we can choose DSA as default key for the server Authentication. Actually, if in the known_hosts file on the client we have the RSA key of the server and if the client is configured to use the DSA key, the server authentication will failed. Because the SSH client searchs only the default key of the server in the known_host file. When we are in this situation, OpenSSH client tell us that there is a key corresponding to the remote host in the known_hosts file but this key is not the default configured for the client. So it doesn't want use it.
As of OpenSSH-5.7, the ssh client will not automatically prefer to use host key types that it actually has hostkeys for. So it should automatically do the right thing and avoid hostkey warnings if the server advertises things in a different way. Unfortunately, the SSH protocol can only attempt one hostkey type per connection and has no way for a server to tell a client its full list of hostkeys. We might look at making a protocol extension in the future to allow the server to tell the client of its full list of hostkeys. For now, you should let the client select the host key algorithm automatically and it will do the right thing. If you want to override the host key algorithm, then it is your responsibility to obtain the other host keys and place them in known_hosts (either manually or by accepting the "new hostkey" message)
err, that should read "As of OpenSSH-5.7, the ssh client will *now* automatically" (i.e. not "not automatically")
close resolved bugs now that openssh-5.9 has been released