There are instances where the user is implied, but there is always a user. As far as Git goes, the user is almost always git.

The public key contains a user name/email address string

No it does not. That is just a comment field.

Technically, you always use a username, however in case of Gitlab that SSH username is always git. When an SSH client connects to server, it offers an authentication method. Gitlab accepts that method only if it is a publickey and the fingerprint of the offered key maps to the known Gitlab user.

Public SSH keys don't contain any user information at all. They could have some metadata for users to easily read, but that can be deleted without repercussions.

I'm no expert, and this is probably how it does NOT work, but if you have a private key, it can generate the public key, so that could be a way to tell the server "this is me", now try me.

Hey I wasn't so far off!

EDIT: Noticed you're talking about Gitlab in the question, and I responded about Github, but I'm certain that gitlab does everything the same way, because that's all the technology is capable of. (I have no way to test the ssh -T command at the end for gitlab, though, so ymmv.)

To clear up some minor confusion here:

1. Github knows nothing about your private key. There's very little metadata stored in the private key, and github.com has access to none of it. That includes email address or identity.
2. Github has identity information stored for you, and then, separately, you uploaded a public key. The public key also contains no information about you, but github knows it's part of your account. Additionally, github enforces a requirement that your public key can't be uploaded to any other account, for the reason I'm about to state below.
3. Github has an index built of everyone's public keys (or more likely their digests, although the technical details of the index are not something known to me--and it doesn't matter). When it sees an authentication request, it looks up the digest in the index, which maps to a user account.

At this point it already knows who is trying to authenticate. Once your authentication request succeeds with your public key (the usual challenge-response handshake associated with asymmetric cryptography), github interacts with your ssh client (most likely git) applying the permissions of your user and your user account.

BTW, github has a documented method for testing the handshake without doing any git operations:

ssh -T git@github.com

Depending on your ssh config, you might also need to supply -i some_filename.pem to this. Github will reply with

Hi aarkon! You've successfully authenticated, but GitHub does not provide shell access.

and then close the connection.

Note that the test authentication uses the username git and, again, contains no information about who you are. It's all just looked up on github's side.

If I'm correct, that would mean that technically, I could authenticate to an SSH server without supplying my name if I use a private key?

Yes.

The public key contains a user name/email address string, I'm aware, is the same information also encoded into the private key as well? If yes, I don't see the need to hand that info to an SSH call. If no, how does the SSH server know which public key it's supposed to use to challenge my private key ownership?

Most of this can be found reading through different Git docs, whether from GitHub, GitLab, Codeberg, Gitea, etc. When using Git you can use different keys for different repos/forges and each has a defined pair, similar to accessing different SSH servers that require specific key pairs. I do understand your questions, but I lack the finesse to explain it since I really only use SSH and Git for my blog and not for anything too complicated.

When authenticating with git over SSH, the private key should be considered secret and well protected.

That means the corresponding public key that was uploaded to the git server is enough to authenticate and no username is required. However, a password protected privare key is possible and extra layers of security can be added to the authentication mechanism.

As far as resource based attacks based on public key searching, I doubt many servers have significant enough public keys on a single host to even notice. Most repos are siloed and have specific teams/individuals assigned to them, so only a small number of public keys even gets loaded.

I dont know enough about the server side mechanics to be sure, but imo the attack surface is pretty small.

It would have to iterate over all saved keys, which sounds rather inefficient to me and potentially unsafe (timing attacks etc.)

sshd only checks for matches in the user's authorized_keys file, not system wide.

I only have experience with Bitbucket, and absolutely none if this may be applicable to you, but we have to generate a key with certain parameters (a minimum) for them to work, and the public key has to be input into a field on your account. So while you do not need to "provide" a username to perform git commands, it is set up in your account as your private key. The command to gen the key is: ssh-keygen -t rsa -m PEM -b 4096 -C "your.email@domain.com"

Once you put your public key into your bitbucket account, using that key will mark all changes you make to you. Is this what you are talking about or am I just off in left field?