Throwing in the class you show is fine, even in the constructor. This is often frowned upon in C++ for various reasons, however, works well in C#.
However you will have to write additional code to bridge the gap between stopping the constructor and stopping the program: this bridge might inform the real user that the input was invalid, and resume to a previous state of the program, asking for input.
That gap is bridged as as @RobertHarvey mentions, with a catch, by some caller (or caller's caller).
However, you don't necessarily want the immediate caller to look for exceptions. If all immediate callers wrapped all calls in try/catch, we'd probably be better off without exceptions at all (using error code returns instead).
You should try to identify the places in the calling code where failure means you are able to somehow retry. There is a bit of an art to this, but should try to think in higher level terms about the job or part of the job that can be aborted when something goes wrong, and what you might want to resume or repeat in those cases. Sometimes, thinking about what the program should do next regardless of whether some job fails or succeeds will help tell you where to handle errors.
In your question you are already indicating the higher level task that you want to retry. Now, it may be that you already have a high level loop in your program so that when it gets good input and succeeds, it doesn't simply quit but ask the user for another input to work on. If you don't have such a loop then you can add one. That high level loop can be a good place to locate the catch. Every iteration of the loop either succeeds (and you inform the user and go again) or it fails, and on failure, you catch, and inform the user, then go again.