Unable to connect with my SSH key, seems that Gitlab thinks I'm someone else

I’ve created a new project and tried to push existing folder, but got The project you were looking for could not be found. error.
I’ve tried to alter the remote url from git@gitlab.com:alechko/project.git to alechko@gitlab.com:alechko/project.git but got Permission denied (publickey). error.

I have several projects that I’ve successfully worked with in the past from the same mac and I’ve double checked that I’ve already setup SSH key from this machine, as pasting my id_rsa.pub into the SSH Keys got me the Fingerprint already taken error.

So I did the ssh -T git@gitlab.com test and for some reason gitlab greets me with a different user: ~/dev ᐅ ssh -T git@gitlab.com Welcome to GitLab, @phil-plencner-hl!

Any idea what’s going on?

Probably you just installed Vagrant.
To fix this

goto nano ~/.ssh/config
and edit like this

Host gitlab.com
Hostname gitlab.com
User <your_gitlab_user>
IdentityFile ~/.ssh/<your_private_key>