You can't always restart a turboprop in flight. You need enough air moving over the blades (e.g. you have to be moving fast enough). How much airflow depends on the engine; every one is different. If you've got the airflow, it doesn't usually take very long but spooling up turboprops to the point where you're generating lift isn't instantaneous. More importantly you have to identify the issue, figure a remediation plan, and execute before you hit the ground. It's how much time you have before you hit the ground that's generally the limiting factor.