Paramiko 2.9.0 breaks compatibility with devices only supporting ssh-rsa and not supporting server-sig-algs

[impact]

paramiko fails to connect to some servers.

[test case]

attempt to connect to a server that does not support server-sig-algs and also only supports ssh-rsa (specifically, does not support rsa-sha2-512). the connection will fail:

DEBUG:paramiko.transport:Finalizing pubkey algorithm for key of type 'ssh-rsa'
DEBUG:paramiko.transport:Our pubkey algorithm list: ['rsa-sha2-512', 'rsa-sha2-256', 'ssh-rsa']
DEBUG:paramiko.transport:Server did not send a server-sig-algs list; defaulting to our first preferred algo ('rsa-sha2-512')
DEBUG:paramiko.transport:NOTE: you may use the 'disabled_algorithms' SSHClient/Transport init kwarg to disable that or other algorithms if your server does not support them!
INFO:paramiko.transport:Authentication (publickey) failed.
Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
  File "/usr/lib/python3/dist-packages/paramiko/client.py", line 435, in connect
    self._auth(
  File "/usr/lib/python3/dist-packages/paramiko/client.py", line 766, in _auth
    raise saved_exception
  File "/usr/lib/python3/dist-packages/paramiko/client.py", line 736, in _auth
    key = self._key_from_filepath(
  File "/usr/lib/python3/dist-packages/paramiko/client.py", line 588, in _key_from_filepath
    key = klass.from_private_key_file(key_path, password)
  File "/usr/lib/python3/dist-packages/paramiko/pkey.py", line 249, in from_private_key_file
    key = cls(filename=filename, password=password)
  File "/usr/lib/python3/dist-packages/paramiko/rsakey.py", line 64, in __init__
    self._from_private_key_file(filename, password)
  File "/usr/lib/python3/dist-packages/paramiko/rsakey.py", line 190, in _from_private_key_file
    data = self._read_private_key_file("RSA", filename, password)
  File "/usr/lib/python3/dist-packages/paramiko/pkey.py", line 322, in _read_private_key_file
    data = self._read_private_key(tag, f, password)
  File "/usr/lib/python3/dist-packages/paramiko/pkey.py", line 351, in _read_private_key
    data = self._read_private_key_openssh(lines[start:end], password)
  File "/usr/lib/python3/dist-packages/paramiko/pkey.py", line 452, in _read_private_key_openssh
    raise PasswordRequiredException(
paramiko.ssh_exception.PasswordRequiredException: private key file is encrypted

[regression potential]

any regression would likely prevent paramiko from connecting to a remote server.

[scope]

this needs to be fixed in jammy and later.

this problem was introduced in paramiko 2.9.0 so does not exist in impish or earlier.

[other info]

this doesn't appear to be fixed upstream yet.
https://github.com/paramiko/paramiko/issues/2012

Note this can be worked around if direct access to the paramiko code is possible, by using the 'disabled_algorithms' parameter to the client connect() method, e.g.:

client.connect("<hostname>", disabled_algorithms={'pubkeys': ['rsa-sha2-256', 'rsa-sha2-512']})

Note this can break connections to other systems however, that do support (only) those algs, so is not a very good workaround. Additionally, this workaround isn't even possible if paramiko is being used internally by some other python application.