If you don't want to write your own plugin, github.com/skuroda/Sublime-AdvancedNewFile already supports it. There isn't a key binding (by default), but there is a command palette entry. You can add a key binding yourself if you want also. The plugin ties into the file creation of the plugin, so it will create any directories not on the path specified. In addition, there is tab completion for the path, which can be convenient.
If you do use the plugin, I'd also recommend adding a user setting for the plugin "rename_default": ":". With this, the path you specify will start from the location of the current file.
Never quite got around to finishing all of the documentation, but what most of it should be in the readme or the wiki (github.com/skuroda/Sublime-AdvancedNewFile/wiki).