It's pretty quick.
From 10.1 of the '328 datasheet:
"If an enabled interrupt occurs while the MCU is in a sleep mode, the MCU wakes up. The MCU is then halted for
four cycles in addition to the start-up time [see 9.2.2], executes the interrupt routine, and resumes execution from the instruction
following SLEEP. The contents of the Register File and SRAM are unaltered when the device wakes up from
sleep. If a reset occurs during sleep mode, the MCU wakes up and executes from the Reset Vector."'
9.2.2:
"To ensure sufficient VCC, the device issues an internal reset with a time-out delay (tTOUT) after the device reset is
released by all other reset sources. ”System Control and Reset” on page 46 describes the start conditions for the
internal reset. The delay (tTOUT) is timed from the Watchdog Oscillator and the number of cycles in the delay is set
by the SUTx and CKSELx fuse bits. The selectable delays are shown in Table 9-2. The frequency of the Watchdog
Oscillator is voltage dependent as shown in ”Typical Characteristics” on page 318."
Table 9-2 shows:
Start up time is fuse programmable for 512 clock cycles, or 8192 clock cycles, approx. 4.1mS [edit - had mA] and 65mS with 5V supply.
"Main purpose of the delay is to keep the AVR in reset until it is supplied with minimum VCC. The delay will not monitor
the actual voltage and it will be required to select a delay longer than the VCC rise time. If this is not possible, an
internal or external Brown-Out Detection circuit should be used. A BOD circuit will ensure sufficient VCC before it
releases the reset, and the time-out delay can be disabled. Disabling the time-out delay without utilizing a Brown-
Out Detection circuit is not recommended."
However, this is the part that seems to apply when waking from Sleep:
"The oscillator is required to oscillate for a minimum number of cycles before the clock is considered stable. An
internal ripple counter monitors the oscillator output clock, and keeps the internal reset active for a given number of
clock cycles. The reset is then released and the device will start to execute. The recommended oscillator start-up
time is dependent on the clock type, and varies from 6 cycles for an externally applied clock to 32K cycles for a low
frequency crystal.
The start-up sequence for the clock includes both the time-out delay and the start-up time when the device starts
up from reset. When starting up from Power-save or Power-down mode, VCC is assumed to be at a sufficient level
and only the start-up time is included."