Had the same issue.

I had multiple public keys in my ~/.ssh/ directory: ~/.ssh/id_rsa.pub, ~/.ssh/id_rsa.gitlab.pub, ~/.ssh/id_rsa.planio.pub

I checked my public key in my SSH Keys settings section und gitlab.com and it matches my id_rsa.gitlab.pub key. So I thought everything should be fine. But still got the Permission denied error when try to push initial project.

Finally the problem was in my ~/.ssh/config file, where I wrongly put these lines:

# gitlab Host gitlab.com Preferredauthentications publickey IdentityFile ~/.ssh/id_rsa

Changed the IdentityFile to ~/.ssh/id_rsa.gitlab and sure it worked!

If you’re running gitlab locally under the docker and run the container with port forwarding (e.g 2224:22) and tried every thing from internet, just try this:

Host gitlab.local
    Preferredauthentications publickey
    IdentityFile ~/.ssh/id_rsa_gitlab_local
    Port 2224
With Port option your git commands will be addressed right to the gitlab container

Instead of gitlab.local you can use any domain or IP address
              
this already solve my problem for case like this, but can i expect the default gitlab creation is pointing to https by default?
This is not the first time i face push failure
Ha, I had GIT_SSH env variable set to C:\Program Files\PuTTY\plink.exe (Windows machine). I tried debug cloning $env:GIT_SSH_COMMAND="ssh -vvv" and it just worked… because ssh.exe is C:\Windows\System32\OpenSSH\ssh.exe
I was puzzled as ssh -T and all other commands vere successfull. But apparantly, git push tried to use plink.exe. Could be documented somwhere I suppose.t
              
Hi, I am also experiencing the same error. using gitlab 14.10.4. I can ssh -T git@IP_ADDRESS but not ssh -T git@FQDN . I am using the same key, same machine where I can connect to git via ssh on ip address. What am I missing?
debug1: Will attempt key: /home/user/.ssh/id_rsa RSA SHA256:VX3JDVrZYNtFpFUhiQR11IYdRCotA/yl/H0DodwKqRY agent
debug2: pubkey_prepare: done
debug1: SSH2_MSG_EXT_INFO received
debug1: kex_input_ext_info: server-sig-algs=<ssh-ed25519,ssh-rsa,rsa-sha2-256,rsa-sha2-512,ssh-dss,ecdsa-sha2-nistp256,ecdsa-sha2-nistp384,ecdsa-sha2-nistp521>
debug2: service_accept: ssh-userauth
debug1: SSH2_MSG_SERVICE_ACCEPT received
debug1: Authentications that can continue: publickey,password
debug1: Next authentication method: publickey
debug1: Offering public key: /home/user/.ssh/id_rsa RSA SHA256:VX3JDVrZYNtFpFUhiQR11IYdRCotA/yl/H0DodwKqRY agent
debug2: we sent a publickey packet, wait for reply
debug1: Authentications that can continue: publickey,password
debug2: we did not send a packet, disable method
debug1: No more authentication methods to try.
git@fqdn: Permission denied (publickey,password).
my setup would be gitlab server is proxied on a separate web server. but I already tried attaching the ip address directly on the gitlab server and still encounter the same error where I can connect to the gitlab server via ssh on ip address, while not via FQDN.
              
Is the DNS record for FQDN pointing to the IP_ADDRESS value? I would guess that you are reaching a different server that does not have the git user configured nor its public key.
Tools such as dig or nslookup can help to verify this locally.
dig FQDN A 
will return the IPv4 address for the given FQDN value. You’ll need to replace FQDN with the real value in the command.
              
Hello everyone, regarding the mentioned problem, I found the same error, but my solution was different.
I did the following steps:

1 - In the upper right menu, click on it and select Preferences.

2 - In Preferences, go to Access Tokens in the left side menu.

3 - In this menu, go to Token Name and assign a name. In Expiration date, to avoid doing it several times, set a long date.

4 - Allow access to what you will allow the token to perform.

5 - Create the token by clicking the “Create Personal Access Token” button.

6 - The token password will appear, so keep it in someplace safe as you will need it.
With this token, test pushing again. This time it will ask for login and password, where the login is your username and the password is the token you just created.
              
Hi @gitlab-greg,
Would you mind to explain me more, I have the same issue with the poster here and I still do not understand why I still failed and got this message when running your solution above:
change-nakes-profession-api
07:24:40.027709 trace.c:314             setup: git_dir: .git
07:24:40.028587 trace.c:315             setup: git_common_dir: .git
07:24:40.028593 trace.c:316             setup: worktree: /Users/raedinurdiansyah/go/src/gitlab.com/raedinurdiansyah/dto-moh/asik/back-office-mirror
07:24:40.028596 trace.c:317             setup: cwd: /Users/raedinurdiansyah/go/src/gitlab.com/raedinurdiansyah/dto-moh/asik/back-office-mirror
07:24:40.028599 trace.c:318             setup: prefix: (null)
07:24:40.028604 git.c:463               trace: built-in: git push --set-upstream origin feat/change-nakes-profession-api
07:24:40.031219 run-command.c:659       trace: run_command: unset GIT_PREFIX; ssh [email protected] 'git-receive-pack '\''raedinurdiansyah/back-office-mirror.git'\'''
remote: 
remote: ========================================================================
remote: 
remote: ERROR: The project you were looking for could not be found or you don't have permission to view it.
remote: 
remote: ========================================================================
remote: 
fatal: Could not read from remote repository.
Please make sure you have the correct access rights
and the repository exists.
the most confusing thing is when I execute ssh -T [email protected], the displayed username is different with my gitlab username. Do you have an idea how I fix this? Thanks before
              
Hi, actually I solved this issue by following gitlab guidelines to create a config file at ~/.ssh like this:
# Company account
Host work
HostName gitlab.com
PreferredAuthentications publickey
IdentityFile ~/.ssh/your_work_ssh_file
# Personal account
Host personal
HostName gitlab.com
PreferredAuthentications publickey
IdentityFile ~/.ssh/your_ssh_file
Then I removed my origin and added the new one with git@<your_host>:username/your_project.git. After that, I pushed my branch, and it was successful. I hope this helps.
              
Hello,
I understand this is a way old post, but it still ranks high in a google search.  So for the sake of brevity, I would like to post an additional solution.  All of the information in this post is good stuff.  However there are quite a bit of assumptions made in regards to an individuals setup.
Here is some info on my setup and what I had to do in order to make SSH work and not just HTTP/S.
I have GITLAB-CE installed to a VM (qemu/kvm).  I am using another VM to develop on, and I wanted to create repos from this system as well.  Not go through the “clone then upload” routine.
My GITLAB-CE server uses the “gitlab.com” repository for its install and updates.  I did customize the sshd_config file on the server where I set a group that was allowed to SSH to the system, and allowed Pubkey authentication.
PubkeyAuthentication yes
AuthorizedKeysFile    .ssh/authorized_keys
AllowGroups sshusers
This config is pretty standard with all my systems.
On my development VM, I had created my key pair and plugged the contents of the .pub file into my account on the GITLAB-CE server (User Settings/SSH Keys).
I don’t log on to my dev machine with the same account name that I use to sign into my gitlab account.  So it took a moment to understand how GITLAB-CE was going to extract my user account when providing a string such as,
git remote add origin [email protected]:group/project.git
Normally a SSH connection would take the form of ssh username@server, so there has to be some trickery at foot in order to properly associate my work on the dev system to my account within GITLAB-CE when using a git@... string.

It did not matter if I set the correct settings within a .gitconfig file nor if I spelled out my credentials in a .git-credentials file.  Those worked for HTTP/S, but not for SSH in my case.
So the ssh key pair needs to match.  The public key .pub that is copied to GitLab needs to match up with the same generated private key.  If the generated key pair are not using the default names (such as id_rsa, id_dsa, id_ecdsa, or id_ed25519) then a config file within the ~/.ssh/ folder needs created under my account on the dev system, in order to identify the correct private key that should be associated with the GitLab server.
Host server.name.ltd
  PreferredAuthentications publickey
  IdentityFile ~/.ssh/server_rsa        # <--- note this is a non-standard name
In a normal run of the mill setup, this would be all that is required to associate the accounts.  When using the git@... address, the keys will match and the server will respond using our user account information.
ssh -T [email protected]
Welcome to GitLab, @phatlix!
Perfect!
But…  this was not working.
created key pair (check)
added public key to gitlab account (check)
created ssh config file in ~/.ssh/ (check)
verified all permissions (check)
additionally verified that I could just ssh normally to the GITLAB-CE server (check)
Soooo.
Earlier I had mentioned that a normal ssh connection uses username@server.  Well, that is still the case.  Nothing has thwarted that concept.  The difference with GitLab is that we are going to make a connection to the GitLab server, using the GitLab user git@..., and once the connection is made, GitLab will handle the account assets and who has access to what.
Earlier I also mentioned that I setup my sshd_config to only allow a certain group to SSH to the server.  Well, now understanding that git@... is a “user” that needs access to the server, I was able to fix my issue by adding the “git” account to my allowed ssh group on the GITLAB-CE server (to be clear: using the OS groups, not within the GitLab configuration).
This took me a hot minute.  So, thought I would share.