Write Access Deploy Key does not work for pushing bag version GIT tag!?

Hi,
I am already bumping my head against the SSH wall for two days, trying to push bag a version bump in the Gitlab CI pipeline back to the original repository on gitlab.com.
I’ve used a ED25519 SSH key pair, like described in the SSH documentation. I used the private key as a pipeline Variable (defined under the project > settings > CI / CD > Variables) and the public key as a Deploy Key (defined under project > settings > repository > Deploy Keys) with write access.

I am trying to generate a new git tag representing the version of the application. It fails with the last command in the script, when trying to push the generated GIT tag back to the original repository.

My .gitlab-ci.yml step looks like this:

version:
  stage: version
  only:
    - master
  except:
    - tags
    - schedules
  script:
    ## Install ssh-agent if not already installed, it is required by Docker.
    ## (change apt-get to yum if you use an RPM-based image)
    - 'which ssh-agent || ( apt-get update -y && apt-get install openssh-client git -y )'

    ## Run ssh-agent (inside the build environment)
    - eval $(ssh-agent -s)

    ## Create the SSH directory and give it the right permissions
    - mkdir -p ~/.ssh
    - chmod 700 ~/.ssh

    ## Add the SSH key stored in SSH_PRIVATE_KEY variable to the agent store
    ## We're using tr to fix line endings which makes ed25519 keys work
    - echo "$CI_SSH_PRIVATE_KEY" | tr -d '\r' > ~/.ssh/id_ed25519
    - chmod 600 ~/.ssh/id_ed25519

    ## Use ssh-keyscan to scan the keys of your private server. Replace gitlab.com
    ## with your own domain name. You can copy and repeat that command if you have
    ## more than one server to connect to.
    - ssh-keyscan gitlab.com >> ~/.ssh/known_hosts
    - chmod 644 ~/.ssh/known_hosts
    - '[[ -f /.dockerenv ]] && echo -e "Host *\n\tStrictHostKeyChecking no\n\n" > ~/.ssh/config'
    
    ##
    ## Optionally, if you will be using any Git commands, set the user name and
    ## email.
    ##
    - git config --global user.email "dario@rfrnz.com"
    - git config --global user.name "Dario Soller"

    - export CI_SSH_REPO_URL=git@gitlab.com:ds_rfrnz/automatic-versioning.git
    - git tag $NEW_VERSION
    - git remote add original-origin $CI_SSH_REPO_URL
    - git remote
    - git push original-origin $NEW_VERSION
  tags:
    - docker
    - gce

The pipeline console output for the last steps looks like this:

$ git tag $NEW_VERSION
$ git remote add original-origin $CI_SSH_REPO_URL
$ git remote
origin
original-origin
$ git push original-origin $NEW_VERSION
Warning: Permanently added the ECDSA host key for IP address '35.231.145.151' to the list of known hosts.
Load key "/root/.ssh/id_ed25519": invalid format
git@gitlab.com: Permission denied (publickey).
fatal: Could not read from remote repository.
Please make sure you have the correct access rights
and the repository exists.

Can someone please point me in the right direction. What I am I doing wrong, or what I am I missing?
Thanks!

Testing the SSH connection, prints the following output:

$ ssh -Tv git@gitlab.com
OpenSSH_7.9p1 Debian-10, OpenSSL 1.1.1c  28 May 2019
debug1: Reading configuration data /root/.ssh/config
debug1: /root/.ssh/config line 1: Applying options for *
debug1: Reading configuration data /etc/ssh/ssh_config
debug1: /etc/ssh/ssh_config line 19: Applying options for *
debug1: Connecting to gitlab.com [35.231.145.151] port 22.
debug1: Connection established.
debug1: identity file /root/.ssh/id_rsa type -1
debug1: identity file /root/.ssh/id_rsa-cert type -1
debug1: identity file /root/.ssh/id_dsa type -1
debug1: identity file /root/.ssh/id_dsa-cert type -1
debug1: identity file /root/.ssh/id_ecdsa type -1
debug1: identity file /root/.ssh/id_ecdsa-cert type -1
debug1: identity file /root/.ssh/id_ed25519 type -1
debug1: identity file /root/.ssh/id_ed25519-cert type -1
debug1: identity file /root/.ssh/id_xmss type -1
debug1: identity file /root/.ssh/id_xmss-cert type -1
debug1: Local version string SSH-2.0-OpenSSH_7.9p1 Debian-10
debug1: Remote protocol version 2.0, remote software version OpenSSH_7.2p2 Ubuntu-4ubuntu2.8
debug1: match: OpenSSH_7.2p2 Ubuntu-4ubuntu2.8 pat OpenSSH_7.0*,OpenSSH_7.1*,OpenSSH_7.2*,OpenSSH_7.3*,OpenSSH_7.4*,OpenSSH_7.5*,OpenSSH_7.6*,OpenSSH_7.7* compat 0x04000002
debug1: Authenticating to gitlab.com:22 as 'git'
debug1: SSH2_MSG_KEXINIT sent
debug1: SSH2_MSG_KEXINIT received
debug1: kex: algorithm: curve25519-sha256@libssh.org
debug1: kex: host key algorithm: ecdsa-sha2-nistp256
debug1: kex: server->client cipher: chacha20-poly1305@openssh.com MAC: <implicit> compression: none
debug1: kex: client->server cipher: chacha20-poly1305@openssh.com MAC: <implicit> compression: none
debug1: expecting SSH2_MSG_KEX_ECDH_REPLY
debug1: Server host key: ecdsa-sha2-nistp256 SHA256:HbW3g8zUjNSksFbqTiUWPWg2Bq1x8xdGUrliXFzSnUw
debug1: Host 'gitlab.com' is known and matches the ECDSA host key.
debug1: Found key in /root/.ssh/known_hosts:2
Warning: Permanently added the ECDSA host key for IP address '35.231.145.151' to the list of known hosts.
debug1: rekey after 134217728 blocks
debug1: SSH2_MSG_NEWKEYS sent
debug1: expecting SSH2_MSG_NEWKEYS
debug1: SSH2_MSG_NEWKEYS received
debug1: rekey after 134217728 blocks
debug1: Will attempt key: /root/.ssh/id_rsa 
debug1: Will attempt key: /root/.ssh/id_dsa 
debug1: Will attempt key: /root/.ssh/id_ecdsa 
debug1: Will attempt key: /root/.ssh/id_ed25519 
debug1: Will attempt key: /root/.ssh/id_xmss 
debug1: SSH2_MSG_EXT_INFO received
debug1: kex_input_ext_info: server-sig-algs=<rsa-sha2-256,rsa-sha2-512>
debug1: SSH2_MSG_SERVICE_ACCEPT received
debug1: Authentications that can continue: publickey
debug1: Next authentication method: publickey
debug1: Trying private key: /root/.ssh/id_rsa
debug1: Trying private key: /root/.ssh/id_dsa
debug1: Trying private key: /root/.ssh/id_ecdsa
debug1: Trying private key: /root/.ssh/id_ed25519
Load key "/root/.ssh/id_ed25519": invalid format
debug1: Trying private key: /root/.ssh/id_xmss
debug1: No more authentication methods to try.
git@gitlab.com: Permission denied (publickey).