Use the low power sleep mode to reduce power consumption if possible and wake the processor up only when it needs to do something; this will give you the very lowest consumption & the oscillator speed is not such a factor in this case. You could also use the WDT (uses a few uA) to wake up the device periodically if desired.
Alternately, if you don't want to use sleep, you can run delays and wait loops at 31kHz and increase the oscillator speed otherwise. This uses considerably more power than either of the above.