Issues when interacting with azure devops repos

Hello,

We are using pygit2 (1.15.0) against repositories hosted on azure devops, and have started seeing issues lately as Microsoft are phasing out ssh-rsa keys: https://devblogs.microsoft.com/devops/ssh-rsa-deprecation

The error message I get when I for example try to clone a repository is this:

_pygit2.GitError: remote: Command git-upload-pack: You’re using ssh-rsa that is about to be deprecated and your request has been blocked intentionally. Any SSH session using SSH-RSA is subject to brown out (failure during random time periods). Please use rsa-sha2-256 or rsa-sha2-512 instead. For more details see https://aka.ms/ado-ssh-rsa-deprecation.
remote: ERROR_SSH_UNSUPPORTED_CIPHER (7)

I have created a new ssh-key according to the specs that Microsoft advice (ssh-keygen -t rsa-sha2-512) and use this key when trying to clone. If I do a manual git clone using the same key, it works without any errors. I have tried to dig into the pygit2 code in order to figure out what is going on but I am stuck.

Any ideas what could be causing this?

Here is the tiny python program that I use for testing:

import pygit2
...
keypair = pygit2.Keypair(username, public_key, private_key, passphrase)
callbacks = pygit2.RemoteCallbacks(credentials=keypair)
pygit2.clone_repository(repo_url, "test", callbacks=callbacks)

Start with the Python reproducer using pygit2.Keypair, RemoteCallbacks, and clone_repository, then compare its SSH negotiation with the successful manual git clone using the same key. Trace where the SSH algorithm is selected and reproduce the Azure DevOps failure. Done means cloning the repository succeeds with rsa-sha2-512 without the SSH-RSA error.