Going to ask a couple silly questions (since those are usually the ones that matter in support)
Are you able to SSH to this server locally using the same private key?
I notice you are using the same key for your other two servers, does that one work if added to CircleCI for the third server?
I really appreciate your patience in troubleshooting, this is a confusing one that seems to have no cause at all. 