If remote server runs sshd with OpenSSH<=7.7 paramiko does the wrong thing when connecting with a CA-signed ssh key (...-cert.pub). This patch fixes that.

auth_handler.patch

--- a/paramiko/auth_handler.py	2022-04-26 15:37:37.433185610 +0200
+++ b/paramiko/auth_handler.py	2022-04-26 15:37:25.083111811 +0200
@@ -22,6 +22,7 @@
 
 import weakref
 import time
+import re
 
 from paramiko.common import (
     cMSG_SERVICE_REQUEST,
@@ -298,6 +299,16 @@
                 key_type
             ),
         )
+        # PATCH: If remote server is OpenSSH <=7.7, always use ssh-rsa-cert-v01@openssh.com.
+        if (
+            key_type.endswith("-cert-v01@openssh.com") and
+            re.search(r'-OpenSSH_(?:[1-6]|7\.[0-7])',
+                      self.transport.remote_version)
+        ):
+            pubkey_algo = "ssh-rsa-cert-v01@openssh.com"
+            self.transport._agreed_pubkey_algorithm = pubkey_algo
+            return pubkey_algo
         # Only consider RSA algos from our list, lest we agree on another!
         my_algos = [x for x in self.transport.preferred_pubkeys if "rsa" in x]
         self._log(DEBUG, "Our pubkey algorithm list: {}".format(my_algos))

trymiko.py

#!/usr/bin/env python3
"""If remote server runs sshd with OpenSSH<=7.7 paramiko does the wrong thing 
when connecting with a CA-signed ssh key (...-cert.pub).

For trying before and after the patch (https://gist.github.com/con-f-use/b9f92a66105d7d6af1944a919a4f0898)"""

import os, sys, logging
import paramiko

def try_connect(hostname, key_path="~/.ssh/id_rsa-cert.pub"):  # change this to your keyfile location
    logging.basicConfig(level=logging.DEBUG, stream=sys.stderr)
    client = paramiko.SSHClient()
    client.set_missing_host_key_policy(paramiko.AutoAddPolicy())
    client.connect(hostname, 22, username="qa", key_filename=os.path.expanduser(key_path), look_for_keys=False)

if __name__ == "__main__":
    try_connect(*sys.argv)