Since 9671352, it seems that public key authentication can only succeed if the key type is also a host key type supported by the server.
I believe that the root cause of this is 9671352#diff-521b24d9ed9094555c19f59ffa14e862R235-R239, where the "signature algorithms" (i.e. server_host_key_algorithms per the SSH spec) are used to populate the factory that is later used to send and sign with public keys.
I would think that that the list of KeyAlgorithm factories should rather be populated directly from the config as it does not require negotiation with the server. KeyedAuthMethod.java would then need to be changed to use those factories instead of asking Transport for them.