'ssh-keygen' is not recognized as an internal or external command

2012:
ssh-keygen.exe is part of msysgit:

 C:\path\to\msysgit1.7.11\bin\ssh-keygen.exe

if your %PATH% includes C:\path\to\msysgit1.7.11\bin\, you will have ssh-keygen.

Update 2015:
ssh-keygen.exe is part of Git For Windows, whose releases include PortableGit-2.4.3.1-2nd-release-candidate-64-bit.7z

c:\path\to\PortableGit-2.4.3.1-2nd-release-candidate-64-bit\usr\bin\ssh-keygen.exe

That means the %PATH% must include c:\path\to\PortableGit-2.4.3.1-2nd-release-candidate-64-bit\usr\bin (without the ssh-keygen.exe)

As I explained before, Git for Windows will soon phase out msysgit.
I detailed in "Why is it that if you download Git 2.0 from the net, you always get a 1.9.4 installer package?" how this new version is based on the more recent msys2 project.

I just had this issue and thought I'd share what I thought was an easier way around this.

Open git-bash and run the same command with the addition of -C since you're commenting in your email address: ssh-keygen -t rsa -C "email@youremail.com" command. That's it.

git-bash should have been installed when you installed git. If you can't find it you can check C:\Program Files\Git\Git Bash

The first time I did this it failed to create the .ssh folder for me so I had to open a standard Command Prompt and mkdir C:\Users\yourusername\.ssh

I followed below in windows (With Git for Windows installed)

1. Run "Git Gui" (Start --> Git --> Git Gui)
2. Click Help and then Show SSH Key
3. Click Generate Key if you do not have one already

Note:- this creates the key files under your personal profile folder C:\Users\YourUserID\.ssh\