Paramiko returns "Bad authentication type", but can connect manually

This is Python code I'm using to connect.

def connect(self):
"""Open connection to remote host."""
try:
    self.client = SSHClient()
    self.client.set_missing_host_key_policy(AutoAddPolicy())
    self.client.connect(self.host,
                        username=self.user,
                        password=self.password,
                        key_filename=self.key_file,
                        timeout=120)
except Exception as error:
    # we fail an attemp - wait or print error and retry
    print(f"MSG: SSH connection failed")
    print(error)
    sleep(1)
else:
    # Everythig ok, continue
    print('MSG: SSH connection established.')
    return self.client

However, I always get the error

Bad authentication type, available options: public key

Two things:

1. Manually from this Ubuntu laptop I can connect to the host without issues

    ssh-add privatekey
    ssh root@host
   

2. The Python script works on other Ubuntu laptops without issues. chmod permissions on the key are set to 600. I've copy pasted the private key file from the other computers to this one without success.

Edit: Adding this line in client.connect params solved the issue.

disabled_algorithms=dict(pubkeys=["rsa-sha2-512", "rsa-sha2-256"])

Alternatively, rolling back to Paramiko 2.7.2 works as well