Refactor to save bytes?
On a quick test build for an ATmega328p type Arduino, the implementation of random() and its unique dependencies seems to be about 180 bytes, so you might see if there's a more compact way of achieving your need there, perhaps using the low byte of some mathematical expression of the time, and just retrying until you get an in-range value.

Of course if you get really stuck, you could remove the bootloader and program it with ISP from an ordinary Arduino or something like that.