Check for the existence of /etc/ssh/sshd_config.d/50-cloud-init.conf and see if it contains a line that enables password login. From askubuntu.com/q/1494410/243321

The first step in debugging ssh connections is to add the -v option to tour ssh command (ssh -v ...). Look at both the client's and server's lists of authentication methods. Only the authentication methods appearing in BOTH lists will work. If your desired authentication method fails, you'll know which server to "fix".

@OrganicMarble, Is sshd_config supposed to configure the server? The server A seems ok: I can establish a connection without a password from B to A. The client C is probably the issue. Besides, I think the problem here is that the key is being ignored since SSH tries the key first, and if it cannot proceed with the key, it asks for the password. Disabling password authentication doesn't seem to make any difference if a key has been provided and everything works as it should.

It pretty clearly is trying the key. Have you actually double checked that the public keys you copied into ~/.ssh/authorized_keys on A are correct? No typos? What do the sshd logs on A shows for the connection attempt you have shown in the question?

And following on from @muru's comment, that the keys were copied to the directory of the correct user. As far as the log goes, when I do it, I don't get the "next authentication method" line in my log for the public key attempt. Did it try some other method first? Could be a version difference, my server is 20.04.

@waltinator, I've added the last part of the log, which appears to be different between B and C. The server A should be ok since it can handle the ed25519 key of the client B. Besides, the ssh_config file is identical for B and C. Is there any other list of authentication methods I need to check?

What is the read/write permissions of the ed25519 private key in C?

As I said in my answer, both lists of authentication methods are in the logfile, before any Next authentication method messages. You have shown a lig fragment of several keys failing in "publickey", and trying password next.

@muru, the public keys in the authorized_keys file seem ok. Besides, apart from checking it, I tried different keys and copied the public keys using the command ssh-copy-id -i .... I've added the A log above.

@OrganicMarble, the line before says only debug1: Authentications that can continue: publickey,keyboard-interactive. The user and the related folder and file permissions should be ok, since they are equivalent in B and C.

@waltinator, from that list, it seems that the client tries the ed25519 key. What could be the reasons for ignoring/not finding the provided key? If beneficial, I can share the previous part of the log. However, it looks the same as for B.

The permissions look good.

Good news. Following @waltinator comments, I tried another key named id_ed25519 and it finally worked! So now my question is why C ignores the key with the name I set. It works on B but it doesn't on C.

I found out how to fix it. Apparently, on C, I need to add a line in etc/ssh/ssh_config to let the client know that there is a key with a non-default name: IdentityFile ~/.ssh/Aserver. After that, it establishes the connection without asking for the password.

Thanks everyone!

You should have included in your question that you have renamed the keys away from default names, since this was the cause of the issue.

Oh, cone on! AskUbuntu is a Q&A site. You askedba question, I provided a debugging method. I'm not going to hold your hand while you struggle.

@ArturMeinild. The problem is that I'm using a non-default name also in B, and there it works. This probably changed between OpenSSH versions 8.9 and 9.6. It's the only difference I'm aware of between B and C and it is reported above.

@waltinator, you asked the right question and that is what matters :)

Please write the solution as an answer, and not in the question. Thanks. 👍