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.