pubkey auth issues with debian 12

[mbchristoff]

sshd on Debian 12 disabled the older ssh-rsa encryption from the handshake for pubkeys.
Thus makes is impossible to login using the old paramiko Debian 11 has in its repo (2.7.2).
Debian 12 on the other hand uses a newer version of paramiko (2.12.0-2) which has the exact opposite effect, it can't login to older clients with <=Debian9.

This change seems to be the culprit:
https://www.paramiko.org/changelog.html#2.9.0

The fix for plain ssh is:

Host *
    HostKeyAlgorithms=+ssh-rsa
    PubkeyAcceptedKeyTypes +ssh-rsa

It seems that using the newer ssh-rsa2 makes the older sshd choke, using ssh-rsa first would solve this.
I tried using "disabled_algorithms" but this only made me able to connect to older or newer clients, never both.
Any suggestions which enables us to connect to new and legacy clients?