WIthout doing an analysis of the houses energy needs, neither one may be the correct size! Under ideal conditions, on the coldest design day, the furnace would run constantly. This provides more comfort and efficiency along with longevity. You lose energy with each cold start, and cycles wear things out faster than duration of operations. Replacing a furnace with a similar sized unit is usually going to result in oversizing - oversizing affects comfort, purchase price, and cost of operation.
Not all furnaces are mulitistage, and then it becomes even more important to size it correctly. Each time it starts up, you'll get a shot of cold air as the furnace heats up the ducts and heat exchanger, then when you shut it off, you lose most of that heat which is why running longer is better. Depending on the house, even 35K is likely more than needed. The only time extra capacity is somewhat useful is to rewarm the house after it has cooled off - then, it can recover quicker. Otherwise, excess capacity is just costing money.