If you're on a network that restricts SSH out (i.e. you are getting connection errors instead of authentication ones), find out if there's an internal server you can hop to first and then SSH out. You'll likely want to set it as a jump host. You should avoid putting your SSH private key anywhere other than your local machine.
Check what your remote username should be from idm.wikimedia.org. Check what username you are actually trying to log in as - if it's not specified on your SSH command (or PuTTY session) and it's not coming from your SSH config (if you have one), it's likely defaulting to the username on your local machine, which may not be the correct username.
Check what SSH keys are on your account. If you're not specifying your key using -i on the command line (or directly in PuTTY), is it in your agent? Check ssh-add -L (or Pageant, for PuTTY users).
For Cloud VPS and Toolforge, you can see the SSH keys on your account at idm.wikimedia.org (other users can find them by running ldapsearch -xLLL uid=<your username> sshPublicKey from inside labs).
Check that your SSH keys are in the right format. Wikimedia should have the OpenSSH-formatted public key, it should not begin 'BEGIN SSH2 PUBLIC KEY' etc. If you're using the OpenSSH command line (ssh on linux hosts) your local private key file should be in OpenSSH format, not SSH2/SSH.com.
