With putty, you can upload public key manually, assuming you now can access the server with username and password:
- Generate the key file, with the guide you followed it will be .pub file, the content of the file should shart with "ssh-rsa AAAA ...."
- Login to the server machine
- Copy the content of the .pub file into the ~/.ssh/authorized_keys file (for this use vim, nano or your favourite text editor)
If your SSH directory does not exist, create it and then copy the pub file into the ~/.ssh/authorized_keys:
mkdir ~/.ssh
chmod 0700 ~/.ssh
touch ~/.ssh/authorized_keys
chmod 0644 ~/.ssh/authorized_keys
nano ~/.ssh/authorized_keys
...
Now you should be able to login with your private key file.