sftp login to a certain server always fails on first attempted method even if it is the correct method

One remote sftp server I need to connect to had an overhaul for upgrading their security.
After that overhaul, it took me a long time to figure out how to connect with paramiko while using the usual command line sftp client on Linux worked.
The first thing I have noticed is that in interactive mode, the new server will reject a sftp connection before asking for a password if the username is not a valid user name (this does not look very secure since it is leaking the username validity).

After many trials and errors, I have realised the following:
the connection will succeed only on the second connection method. So for example if I want to connect via password, I give it a key and a password, which fails on the first try with the key but then succeeds using password.
If I want to connect via key, I give it any key, I place the valid key in ~/.ssh/id_rsa and I use the option look_for_keys, the first try is with the user provided key (which fails even if this is a valid key) but then it tries the default key ~/.ssh/id_rsa (because of the option look_for_keys) and succeeds.

It looks like the username validation is done by a server which hides the sftp server until after the username is validated but because paramiko sends the username and credentials together, it always gets rejected on the first try.
Now the problem I have is that my workaround requires me to use ~/.ssh/id_rsa and on our system that key is used by many other applications/scripts and now I have to modify that file depending on which application is using it: I am writing a script to connect to the server which sets and reset id_rsa. This is not very practical and safe. So I would prefer, if I could tell paramiko to attempt twice the same key or send the username first and credentials only after aknowledgment of reception of the username.
Is there a way to do this?
Thank you

Start by reproducing the reported SFTP authentication behavior with a server that rejects the first authentication method, comparing Paramiko with the Linux sftp client. Trace the authentication exchange and determine whether retrying the same key or separating username submission from credentials is supported. Done means the connection works without modifying ~/.ssh/id_rsa, with regression coverage for the reported sequence.