"fatal: Could not read from remote repository." when using ED25519 SSH key

Summary

I created a Gitlab user, added the user to my group, created an ED25519 SSH key using ssh-keygen -t ed25519, and added the public key to the user's SSH keys. The user is unable to push changes to a repo. Here is the error:

# git push
The project you were looking for could not be found.
fatal: Could not read from remote repository.

Please make sure you have the correct access rights
and the repository exists.

If I create an RSA SSH key using ssh-keygen (RSA is the default), and add the public key to the user's SSH keys in Gitlab, then the user can push changes.

Steps to reproduce

  1. Create a Gitlab user.
  2. Create an ED25519 key with ssh-keygen -t ed25519
  3. Add the ED25519 SSH public key to the user's SSH keys in Gitlab.
  4. Create an RSA key with ssh-keygen
  5. Add the RSA SSH public key to the user's SSH keys in Gitlab.
  6. Do something like this:
# echo '-----BEGIN OPENSSH PRIVATE KEY-----
> b3BlbnNzaC1rZXktdjEAAAAABG5vbnUAAAAEbm9uZQAAAAAAAAABAAAAMwAAAAtzc2gtZW
<redacted>
> p73nrKKwCnj9c5j0x0OoAAAACmNvZGVmaS1ib3QBAgM=
> -----END OPENSSH PRIVATE KEY-----' | tr -d "\r" | ssh-add -
Identity added: (stdin) (test-account)
# ssh-add -l
256 SHA256:LXdFYN23oUm2lQfnNhsmX5uBQvACnjF8OoxVzi4Q8wM test-account (ED25519)
# git rm test.yaml 
rm 'test.yaml'
# git commit -m 'Removing test.yaml'
[master 85a59b3] Removing test.yaml
 1 file changed, 0 insertions(+), 0 deletions(-)
 delete mode 100644 test.yaml
# git push
The project you were looking for could not be found.
fatal: Could not read from remote repository.

Please make sure you have the correct access rights
and the repository exists.
# ssh-add -D
All identities removed.
# echo '-----BEGIN OPENSSH PRIVATE KEY-----
> b3BlbnNzaC1rZXktdjEAAAAABG5vbmUAAAAEbm9uZQAAAAAAAAABAAABFwAAAAdzc2gtcn
<redacted>
> 6Q9HD0889AZvSjv3AAAACmNvZGVmaS1ib3Q=
> -----END OPENSSH PRIVATE KEY-----' | tr -d "\r" | ssh-add -
Identity added: (stdin) (test-account)
# git push
Enumerating objects: 3, done.
Counting objects: 100% (3/3), done.
Delta compression using up to 4 threads
Compressing objects: 100% (2/2), done.
Writing objects: 100% (2/2), 230 bytes | 230.00 KiB/s, done.
Total 2 (delta 1), reused 0 (delta 0)
To gitlab.com:test-org/test.git
   b74ccd2..85a59b3  master -> master
#
Edited by Kyle Smith