OpenSSH has quite a lot of things involving keys, key types, and key algorithms, with options to control them and ways to report on them and so on. It can be confusing when you read manpages for ssh, ssh_config, sshd, and so on (and it has regularly confused me). It turns out that OpenSSH has a great explanation in their OpenSSH Legacy Options documentation, so great that rather than paraphrase it I am just going to quote it (with some additional commentary):

When an SSH client connects to a server, each side offers lists of connection parameters to the other. These are, with the corresponding ssh_config keyword:

• KexAlgorithms: the key exchange methods that are used to generate per-connection [symmetric encryption] keys
• HostkeyAlgorithms: the public key algorithms accepted for an SSH server to authenticate itself to an SSH client
• Ciphers: the ciphers to encrypt the connection
• MACs: the message authentication codes used to detect traffic modification

When a SSH connection is established, the client and server use the SSH transport protocol to create the initial set of symmetric encryption keys that will encrypt the entire conversation going forward, and in the process the client verifies the server's host key (only one key out of the keys the server offers). If a server supports multiple host key types, in theory the client controls which one will be used based on the order of its HostkeyAlgorithms.

The KexAlgorithms 'key exchange methods' have nothing to do with the public key algorithms used for host key verification, although they do use related cryptographic techniques. How they work in specific is covered in various RFCs and other documentation linked from OpenSSH's Specifications page. This can be initially confusing since some of the KEX algorithm names look a bit similar to key type names (eg 'curve25519-sha256' and 'ecdh-sha2-nistp384').

Once the SSH transport protocol has been successful, the SSH client will go on to request user authentication, where some additional options come into play (again quoting the OpenSSH documentation):

• PubkeyAcceptedKeyTypes (ssh/sshd): the public key algorithms that will be attempted by the client, and accepted by the server for public-key authentication (e.g. via .ssh/authorized_keys)
• HostbasedKeyTypes (ssh) and HostbasedAcceptedKeyTypes (sshd): the key types that will be attempted by the client, and accepted by the server for host-based authentication (e.g via .rhosts or .shosts)

(This public key authentication is strongly protected against attacker in the middle attacks.)

A modern ssh command supports 'ssh -Q <thing>' to query various cryptography related things, and you can also use ssh_config and sshd_config option names as well. As far as I know, this doesn't look at your actual SSH configuration files; instead, it reports what your OpenSSH could support if you enabled everything. By extension it doesn't necessarily list public key algorithms in your preference order. As far as I know, there's no way to get OpenSSH to tell you the state of client or server configurations; you get to read your configuration files and anything else necessary on your systems.

If I'm right, this means that 'ssh -Q HostkeyAlgorithms', 'ssh -Q HostbasedKeyTypes', and so on will always give you the same list, even if you have them configured differently. I believe they're all aliases for 'ssh -Q key-sig'. Not all of the 'ssh -Q' features have ssh and sshd configuration option aliases, either, I believe including 'ssh -Q key' (and its kin like 'key-plain'), which give you the list of key types instead of key signature algorithms. Note that there really are three different types of ECDSA keys, contrary to what I thought yesterday (see the comments on that entry).

PS: You can set HostkeyAlgorithms in sshd_config on the server as well as in the client, and I guess you could use this to turn off offering "ssh-rsa" to clients right now (and at some point in the future you may need to use it to turn "ssh-rsa" back on, when OpenSSH deprecates this key signature scheme). Generally you control what host key algorithms you offer to clients by what keys you generate for sshd, since most keys have only one key signature algorithm (including ECDSA keys, as mentioned).