What will help battery performance is not wasting a lot of battery capacity making heat with the 5V regulator.
Look into a switching stepdown regulator if you are really stuck using a 9V battery (like the square ones which have relatively little capacity).
Some examples, with different current capacities:
Then think about running from LiPOs, NiMH, some kind of rechargeable battery.
I purhcased a 1000mAH LiPO from www.gravitech.us for $12 and use it to power an RF remote control (had to ask for it, doesn't appear on their webpage) and use a MAX1811 charge control chip to recharge from a 5v source.