Your home is going to take X amount of btu's/hr (energy) to bring it back to temperature. This amount isn't dependant on the efficiency of the furnace, it's 100% dependant on the home.
So to answer your question: the home will take X amount of time to come up to the higher temperature based on home's heat load/output of furnace, not on the temperature of the outlet air temperature of the furnace.
If the old furnace and the new furnace are equal in their input ratings the home will actually get to temperature quicker because the increased efficiency of the new furnace puts more of the energy used into the home instead of up a chimney.
As a side note, you might want to check with the installing contractor and read through your owners manual for the new furnace. Some furnace manufacturers limit the lowest temperature that the return air can be coming back to the furnace. Setting the temperature to low in the home may void the warranty on the furnace.
Use the biggest hammer you like, pounding a square peg into a round hole does not equal a proper fit.