PythonのParamikoを使って、以下のようなコードで接続しようと試みたところ。。。

Python

import os
import paramiko

config_file = os.path.join(os.getenv('HOME'), '.ssh/config')
ssh_config = paramiko.SSHConfig()
ssh_config.parse(open(config_file, 'r'))
config_file = ssh_config.lookup('レガシーなバージョンの接続先サーバー')

ssh_client = paramiko.SSHClient()
ssh_client.load_system_host_keys()
ssh_client.set_missing_host_key_policy(paramiko.AutoAddPolicy())
ssh_client.connect(
    hostname=config_file['hostname'],
    username=config_file['user'],
    port=config_file['port'],
    key_filename=config_file['identityfile'],
    sock=paramiko.ProxyCommand(config_file['proxycommand']),
)

stdin, stdout, stderr = ssh_client.exec_command('cat /etc/os-release')
stdin.close()
for line in stdout:
    print(line.strip())

ssh_client.close()

このようなエラーが発生して接続に失敗します。

Traceback (most recent call last):
  File "search_sni_1ip.py", line 23, in <module>
    sock=paramiko.ProxyCommand(config_file["proxycommand"]),
  File "/usr/local/lib/python3.7/site-packages/paramiko/client.py", line 446, in connect
    passphrase,
  File "/usr/local/lib/python3.7/site-packages/paramiko/client.py", line 766, in _auth
    raise saved_exception
  File "/usr/local/lib/python3.7/site-packages/paramiko/client.py", line 742, in _auth
    self._transport.auth_publickey(username, key)
  File "/usr/local/lib/python3.7/site-packages/paramiko/transport.py", line 1634, in auth_publickey
    return self.auth_handler.wait_for_response(my_event)
  File "/usr/local/lib/python3.7/site-packages/paramiko/auth_handler.py", line 258, in wait_for_response
    raise e
paramiko.ssh_exception.AuthenticationException: Authentication failed.

Paramiko経由でのSSH接続は失敗するが、コマンドラインでのsshコマンドだと接続できるという状況。
また、上記のコードで接続できるサーバーもあるので、もしかすると接続先のサーバーのOpenSSHのバージョンの違いによる問題ではないかと予想しました。

そこで、「Paramikoのssh認証でハマった話」という記事を発見。
OpenSSHのバージョン違いによる問題に言及されていたので、完全にこれだろうと意気揚々とSSHの鍵を作り変えて試してみるが。。。失敗。ということでSSHの鍵の問題ではないことがわかりました。

次に、「paramiko old connect fail」といったキーワードでググってみると、「Key auth on paramiko 2.9.0+ fails to connect to older hosts」というAnsibleのIssueを発見。Ansibleは接続にParamikoを利用しているので、かなり有力な情報です。
このIssueの中に「 Paramiko's SSHClient added support for disabled_algorithms back in their ~2.6 release, 」という記述があります。
どうやらParamikoのバージョンアップに伴い、レガシーなサーバーに接続する際には、SSHClientメソッドの引数に「 disabled_algorithms 」という引数を渡す必要があるということがわかりました。

同じようなキーワードでさらにググってみると、「RSA key auth failing from paramiko 2.9.x client to dropbear server」というParamiko自体のIssueを発見しました。
この中で「 disabled_keys = {'pubkeys':['rsa-sha2-512','rsa-sha2-256']} does work around the issue, 」という記述があり、SSHClientメソッドの引数でこれを渡すことで動きそうなことがわかりました。
この件については、Paramiko 2.9.0のChangelogの中で「 When the server does not send server-sig-algs, Paramiko will attempt the first algorithm in the above list. Clients connecting to legacy servers should thus use disabled_algorithms to turn off SHA2. 」との注意書きがあるので、この対応でどうやら間違いなさそうです。

対応方法がわかったので、connectメソッドに引数「 disabled_algorithms 」を追加しました。

Python

ssh_client.connect(
    hostname=config_file['hostname'],
    username=config_file['user'],
    port=config_file['port'],
    key_filename=config_file['identityfile'],
    sock=paramiko.ProxyCommand(config_file['proxycommand']),
    disabled_algorithms=dict(pubkeys=['rsa-sha2-256', 'rsa-sha2-512']),
)

修正したプログラムを実行してみると、無事に「 cat /etc/os-release 」の結果が返ってきました。

NAME="Amazon Linux AMI"
VERSION="2014.09"
ID="amzn"
ID_LIKE="rhel fedora"
VERSION_ID="2014.09"
PRETTY_NAME="Amazon Linux AMI 2014.09"
ANSI_COLOR="0;33"
CPE_NAME="cpe:/o:amazon:linux:2014.09:ga"
HOME_URL="http://aws.amazon.com/amazon-linux-ami/"