We present a two-stage stochastic integer program for assigning Certified Registered Nurse Anesthetists (CRNAs) to Operating Rooms (ORs) under surgery duration uncertainty. The proposed model captures the trade-offs between CRNA staffing levels, CRNA handovers and under-staffing in the ORs. Since the stochastic program includes binary variables in both stages, we present an Integer L-shaped Algorithm to solve the model that incorporates LP Benders Cuts in addition to the standard no-good cuts. To further accelerate convergence, we strengthen these LP Benders Cuts by tightening the second-stage formulation. To this end, we derive valid inequalities for the second-stage problem and show that they describe the convex hull of a binary set defined by a subset of the second-stage constraints. An extensive computational study, based on the data from our partner institution, reveals that our proposed solution approach efficiently solves realistic problem instances to 0.01-optimality, underscoring the effectiveness of the proposed valid inequalities. Additionally, through sensitivity analysis, we provide insights into the trade-offs between CRNA staffing levels, CRNA handovers and under-staffing.