If you have the time you should really get multiple quotes. J&A isn't a contractor I'd consider using, their main business is home warranty companies so they may be overcharging to make up for the low payouts from the warranty companies.

Cost is going to depend on how efficient a furnace you need, if they're having to do any other work, etc.