Cannot ssh into a GCP Virtual Machine via jenkins as a non root user

I have two GCP Virtual Machines. One is an Ubuntu Bionic VM which has a jenkins container in it and the other is a Debian Buster VM. I've been given a fixed key pair in case I want to ssh through jenkins to any other VMs. The key pair were not created as a root user. I'm trying to ssh into the Debian VM via jenkins as a non root user (jenkins) using these key pairs. Here's what all I tried and failed -

1. I copied the public key to /home/jenkins/.ssh/authorized_keys and pasted the public key in the GCP console (Compute Engine > Meta data > ssh keys). Then I created new credentials in Manage Jenkins > Manage Credentials > Global Credentials (Unrestricted) and pasted the private key there. When I go to Manage Jenkins > Configure Systems > SSH remote hosts and enter the target IP and click on Check connection, I get 'can't connect to server'.

2. I tried ssh-copy-id -i ~/.ssh/public-key.pub jenkins@host to transfer the public key to the target server. I get Permission denied (publickey).

3. I tried to create a new key pair in my jenkins VM as user jenkins and tried the above two steps. I get Permission denied (publickey).

4 I changed the permissions of the .ssh folder and the authorized_keys file in the target VM using:

chown -R jenkins:jenkins /home/jenkins/.ssh
chmod 700 /home/jenkins/.ssh
chmod 600 /home/jenkins/.ssh/authorized_keys

Still I get Permission denied (publickey).

5. I cant ssh into the target system using ssh -i path/to/private-key jenkins@target_IP_address (Doesnt work for either key pairs.)

6 I created a config file in my jenkins VM in the path /home/jenkins/.ssh containing the follwing -

Host kanban
Hostname target_IP_address
User jenkins
PubKeyAuthentication yes
IdentityFile /home/jenkins/.ssh/private_key

I cant make head or tail of the logs. Here's a sample -

Feb 27 11:55:00 q-jenkins sshd[15451]: Unable to negotiate with random_IP_address port 56982: no matching key exchange method found. Their offer: diffie-hellman-group1-sha1 [preauth]
Feb 27 11:55:00 q-jenkins sshguard[1102]: Blocking random_IP_address for 1680 secs (4 attacks in 3 secs, after 2 abuses over 853464 secs)
Feb 27 11:56:30 q-jenkins sshd[15498]: Did not receive identification string from 46.19.139.18 port 41788
Feb 27 11:56:36 q-jenkins sshd[15499]: Invalid user user from random_IP_address port 54344
Feb 27 11:56:36 q-jenkins sshd[15499]: Received disconnect from random_IP_address port 54344:11: Normal Shutdown, Thank you for playing [preauth]
Host kanban
Feb 27 13:30:56 q-jenkins sshd[18221]: Received disconnect from random_IP_address port 53044:11: Bye Bye [preauth]
Feb 27 13:30:56 q-jenkins sshd[18221]: Disconnected from authenticating user daemon random_IP_address port 53044 [preauth]
Feb 27 13:52:58 q-jenkins sshd[18887]: Did not receive identification string from random_IP_address port 37348
Feb 27 13:57:50 q-jenkins sshd[19010]: Connection closed by authenticating user root random_IP_address port 54240 [preauth]
Feb 27 14:17:01 q-jenkins CRON[19543]: pam_unix(cron:session): session opened for user root by (uid=0)
Feb 27 14:17:01 q-jenkins CRON[19543]: pam_unix(cron:session): session closed for user root
Host kanban
Feb 27 14:22:35 q-jenkins sshd[19696]: Received disconnect from random_IP_address port 53386:11: Bye Bye [preauth]
Host kanban
Feb 27 14:22:35 q-jenkins sshd[19696]: Disconnected from authenticating user root random_IP_address port 53386 [preauth]
Host kanban
Feb 27 14:31:29 q-jenkins sshd[19954]: Received disconnect from random_IP_address port 6386:11: Bye Bye [preauth]
Feb 27 14:31:29 q-jenkins sshd[19954]: Disconnected from random_IP_address port 6386 [preauth]
Feb 27 14:32:45 q-jenkins sshd[19986]: Accepted publickey for gautam from random_IP_address port 36005 ssh2: ECDSA SHA256:dV7zC4GDrbvAOM+hCJGn6Mjw5gP3+yxEsAGUXA0R6eY
Feb 27 14:32:45 q-jenkins sshd[19986]: pam_unix(sshd:session): session opened for user gautam by (uid=0)
Feb 27 14:32:45 q-jenkins systemd-logind[1367]: New session 1339 of user gautam.
Feb 27 14:32:45 q-jenkins systemd: pam_unix(systemd-user:session): session opened for user gautam by (uid=0)
Feb 27 14:41:21 q-jenkins sshd[20363]: Received disconnect from random_IP_address port 57054:11: Bye Bye [preauth]
Feb 27 14:41:21 q-jenkins sshd[20363]: Disconnected from authenticating user ubuntu random_IP_address port 57054 [preauth]

I've been at this from many days. Somebody please help.

Thanks a lot in advance.