Um, connect to WHAT exactly?  A random server?

When using Putty to SSH into an Ubuntu box, you should know 3 things:

1)  SSH server needs to be installed on Ubuntu (it isn't by default):  sudo apt-get install openssh-server
2)  You won't need to generate any keys
3)  You will just use Putty to connect via SSH to the IP address of the server

If the above is working, and you now want to use public/private keys to connect, instead of a password, then follow this tutorial:

http://blog.padraigkitterick.com/2007/09/16/using-putty-ssh-keys-with-openssh-on-ubuntu