I figured it out. You need to set GIT_SSH environment variable on your machine to point to plink.exe. This could be the one installed with TortoiseHg / TortoiseGit / Git Extensions or you can download it from Putty Download Page, but just make sure that you use the same one system wide. Best to log out from your Windows session to make sure this variable gets set for all Explorer instances and command windows.
For those looking for a detailed explanation have a read of this blog post. Below is a quote from the blog post. Ultimately the ssh-agent.exe needs to be in the path, or resolved some other way.
EDIT:
It appears most of the people don't bother reading the linked blog and the original extract did not quote the full solution, so I've expanded the quote from the blog below.
There are numerous ways to resolve the error, based on the likes to all other answers. One known to work is quoted below. Scan though other answers they may be more appropriate for you.
When I restarted my PowerShell prompt, it told me it could not start SSH Agent.
It turns out that it was not able to find the “ssh-agent.exe” executable. That file is located in C:\Program Files (x86)\Git\bin. but that folder isn’t automatically added to your PATH by msysgit.
If you don’t want to add this path to your system PATH, you can update your PowerShell profile script so it only applies to your PowerShell session. Here’s the change I made.
You can add two lines to the top of your profile (type ise $profile) to fix this PoshGit issue without polluting your Path. Then run . $profile to reload your profile.