If you have a sufficient supply of wood, your new stove may take up the slack. on the other hand, it wouldn’t hurt to have a large enough furnace for those times when you don’t feel like tending the fire.
There are a few things about your situation that I don’t know which could affect the installation costs of a new furnace, for exmple, is your new addition ducted into the existing furnace? If so, then installation costs should be considerably lower. You might also take this opportunity to upgrde to a more efficient furnace. Your current furnace uses 70,000 btuH of gas and delivers 56,000 btuH of heat. A new 90+%, 85,000 btuH furnace would give you over 76,000 btuH of heat.
I did a little (very little) searching and found this listing at Grainger - 80,000 btuH input, 75,000 btuH output, 94.3% efficiency, retail cost $967.00. And Grainger is not the cheapest place around.
I know nothing about building codes or labor rates in Minnesota, but if you know that the furnace costs under $1000, you should be able to swing a reasonable price for installation. And the increased efficiency will help offset the cost over the next few years if gas prices continue to rise. There might even be some rebates available from your gas supplier for buying a high-efficiency furnace.