When trying to connect to my server with Paramiko, I just get Authentication failed..
Looking at the server logs, I see:
userauth_pubkey: key type ssh-rsa not in PubkeyAcceptedKeyTypes [preauth]

The connection works fine using openssh with the same key, so it looks like Paramiko doesn't use rsa-sha2-512/256.