Careful here, the stochiometric ratio is independent of air pressure. A locomotive at high altitude would operate at the same steam gauge pressure, and hence produce the same power as at low altitude. I agree that the fire will produce less heat at higher altitude. However, only if the fire was unable to produce enough energy would the power of the steam engine be significantly reduced, but I expect that most fires in steam engines have ample reserve capacity to produce sufficient heat. 
By way of contrast, a 20% reduction in air pressure presumably would give about a 20% reduction in power in an internal combustion engine, unless super or turbocharged.