Gentoo, latest available openssh package installed this morning.

# equery l openssh
 * Searching for openssh ...
[IP-] [  ] net-misc/openssh-7.9_p1-r4:0

I have a pub key that I use for automated logins, with restrictions in the server-side authorized_keys file:

2048 SHA256:[fingerprint] [ID-string] (RSA)

The last working entry from the server logfile shows:

Apr 18 09:33:01 [myserver] sshd[25210]: Accepted publickey for mhill from [client-ip] port 53628 ssh2: RSA SHA256:xQw4LejbMPRREe7kI/Iz31Nxl07qin+7oZEwm1IXS+s
Apr 18 09:33:01 [myserver] sshd[25210]: pam_unix(sshd:session): session opened for user mhill by (uid=0)

After upgrading from 7.7p1 to 7.9p1, I saw errors in the logfile:

Apr 18 10:01:05 [myserver] sshd[3335]: pam_unix(sshd:auth): authentication failure; logname= uid=0 euid=0 tty=ssh ruser= rhost=[client-ip]  user=mhill
Apr 18 10:01:07 [myserver] sshd[3331]: error: PAM: Authentication failure for mhill from [client-ip]

Investigating, I found the following in the log for each login attempt:

Apr 18 10:01:02 [myserver] sshd[3331]: userauth_pubkey: key type ssh-rsa not in PubkeyAcceptedKeyTypes [preauth]

Funny...

# grep ^PubkeyAcceptedKeyTypes /etc/ssh/sshd_config
PubkeyAcceptedKeyTypes ssh-ed25519-cert-v01@openssh.com,ssh-ed25519,ssh-rsa-cert-v01@openssh.com,ssh-rsa
# sshd -T -f /etc/ssh/sshd_config | grep -i pubkey
pubkeyauthentication yes
pubkeyacceptedkeytypes ssh-ed25519-cert-v01@openssh.com,ssh-ed25519,ssh-rsa-cert-v01@openssh.com,ssh-rsa

Finally, running sshd in debug mode:

debug3: /etc/ssh/sshd_config:640 setting PubkeyAcceptedKeyTypes ssh-ed25519-cert-v01@openssh.com,ssh-ed25519,ssh-rsa-cert-v01@openssh.com,ssh-rsa
[...]
debug1: userauth-request for user mhill service ssh-connection method publickey [preauth]
debug1: attempt 1 failures 0 [preauth]
debug2: input_userauth_request: try method publickey [preauth]
userauth_pubkey: key type ssh-rsa not in PubkeyAcceptedKeyTypes [preauth]
debug2: userauth_pubkey: authenticated 0 pkalg rsa-sha2-512 [preauth]
debug3: user_specific_delay: user specific delay 0.000ms [preauth]
debug3: ensure_minimum_time_since: elapsed 0.070ms, delaying 8.278ms (requested 8.349ms) [preauth]
debug3: userauth_finish: failure partial=0 next methods="publickey,keyboard-interactive" [preauth]
debug3: send packet: type 51 [preauth]
debug3: receive packet: type 50 [preauth]
debug1: userauth-request for user mhill service ssh-connection method keyboard-interactive [preauth]
debug1: attempt 2 failures 1 [preauth]

All indications are that ssh-rsa is listed in PubkeyAcceptedKeyTypes, yet sshd fails the login attempts as though it were not.