Openssh : keys generated on ssh server or ssh client

Q1 : basic question:
I have a Windows 2003 running Openssh server & a Linux box (ssh client).
The Linux box is the one that initiate sftp/ssh/scp connection to the Windows
box.  I would like to use key authentication, so are the private+public keys
generated (ie ssh-key-gen) on Windows 2003 or on the Linux box?

Q2:
If the keys are generated on the Windows 2003 Openssh (Ver 3.8p1-1), can
 someone provide the steps to generate the keys & how should the key be
added/processed on the Linux box to enable the Linux box to ssh into the
Windows 2003  box using the keys (ie no password needed)

Q3:
If the keys are generated on the Linux box (RHES 4.5), what's the command
to generate the keys & how should the keys be added/installed on the
Win 2003 box so that the Linux (ssh client) can ssh into the Windows box
without password (ie keys authentication