Alt+F, W, F.
Unless some crappy application integrated itself into the shell and moves the F away from Folder under the "New..."
Sometimes you don't even get that far. Can you spot which crappy application messed this up?
What gets me is the inconsistency. Sometimes you have an icon you can click for a new folder but no obvious keyboard shortcut, and sometimes it's the other way round. I'm sure Explorer used to have an icon for a new folder, but they quietly retired it.