The UpdateHostKeys feature is designed to only add host key fingerprints to known_hosts if the corresponding signature algorithm is allowed by the HostKeyAlgorithms setting (see client_input_hostkeys() in clientloop.c). However, for RSA keys it only checks HostKeyAlgorithms for the presence of ssh-rsa. If HostKeyAlgorithms includes rsa-sha2-{256,512}, but not ssh-rsa, RSA keys are ignored even though they could be used for authentication.
Created attachment 2961 [details] Accept RSA keys if HostkeyAlgorithms contains rsa-sha2 key types This patch accepts RSA keys if the HostkeyAlgorithms contains rsa-sha2-* keytypes.
Patch applied. This will be in OpenSSH 7.5
Close all resolved bugs after release of OpenSSH 7.7.