Since you’re running into limits on the number of identities you can offer, and some of them are from the host keys, it would be nice to control what client host keys you offer to the server. Or at least to understand where this is set and why, for example, ‘ssh -v’ says that you’re offering a ‘ecdsa-sha2-nistp256’ host key when you don’t even use ECDSA. Unfortunately, todayall of this is underdocumented and it’s somewhat hard to control, although not impossible.
Based on reading the source code, the decisions about what host keys to try to sign and where to find them are split between ssh-keysign and ssh itself, although in a confusing way. Both ssh and ssh-keysign look for the default, traditional names of the host keys (such as /etc/ssh/ssh_host_rsa_key) and determine what host keys to offer based on a combination of what files are present and what host key algorithms ssh likes. Ssh-keysign is ultimately responsible for reading the keys, so what it looks for and finds limits what ssh can ask for.
(Both ssh and ssh-keysign hard code these key paths, although the ssh-keysign source code has a comment that it should use your sshd_config to determine the key paths.)
There are twoways to control what host keys are ultimately used, the brute force way and the nominally correct way. The brute force way is to entirely remove (or rename) the host key files in /etc/ssh for the host key types you don’t use. For example, if you don’t use ECDSA keys and set HostKey in your sshd_config to exclude them, remove /etc/ssh/ssh_host_ecdsa_key* (which was probably created automatically by, for example, the Ubuntu Linux installer).
The nominally correct way is to change what hostbased authentication algorithms ssh will try to use (well, ask ssh-keysign to use), which is controlled by the HostbasedAcceptedAlgorithmsdirective from ssh_config (in older OpenSSH versions, this is called HostbasedKeyTypes instead). You can set this to a restricted list, or you can use the OpenSSH ‘-‘ syntax to remove some algorithms, for example:
The host keys that your ssh will offer to the server for hostbased authentication are those keys that are both available under their standard names in /etc/ssh and allowed by HostbasedAcceptedAlgorithms. Note that some key types can be used by more than one algorithm; working out what algorithms you need to disallow is left as an exercise.
(As you’d expect, this doesn’t affect what key algorithms can be used for personal keys. If you want to use personal ECDSA keypairs, you still can.)