This sounds like a self-correcting problem, if you don't allow immigration. Schools will have to pay more for teachers, which will raise salaries for native born teachers, instead of paying a lower rate to someone on a temporary work visa.

The matter is a little more complicated than that, because Alaska also has some of the nation's most stringent licensure requirements with no alternative routes for high-demand low-supply subject area teachers. You could probably relax those artificial barriers to employment and get more Alaskans teaching without raising the salary as much as if you kept the licensure requirements. You could also promise student debt relief for teachers who serve in rural areas for a certain length of time.