How does OpenSSH determine the choose the host key algorithm?

Question

After updating raspbian and all of its libraries I noticed something different about SSH. When I delete the 'known hosts' file in my home and ssh into my box it provides me with the hosts public key like always however this time I see:

ecdsa-sha2-nistp256 SHA256:xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx

I swear it always gave me an RSA key type a few months back. Why did this change and how does the server decide which public key fingerprint from /etc/ssh/ to give the user connecting?

ssh --version on client linux mint 18 machine outputs OpenSSH_7.2p2 Ubuntu-4ubuntu1, OpenSSL 1.0.2g-fips 1 Mar 2016 and host outputs OpenSSH_6.7p1 Raspbian-5+deb8u3, OpenSSL 1.0.1t 3 May 2016

Solution

The client can specify the hostkey algorithm it prefers with the option HostKeyAlgorithms in ssh_config or ~/.ssh/config or on the command line. man ssh_config on your system to see the default HostKeyAlgorithms preference for your version of openssh. The server will use the first key type which is on the client's list and exists on the server.

If you would prefer to keep the old RSA key challenge, add "-oHostKeyAlgorithms=ssh-rsa" to the command line, or add the line

HostKeyAlgorithms ssh-rsa

to your ssh configuration file(s).