CTR mode nonce with aggressive key rotation policy I'm writing a small encryption library which will be required to use the shortest possible amount of overhead for describing ciphertexts. I want to use CTR mode with a 6-byte random nonce. 

Normally I would never disregard best practices like this, but I think in this context it is acceptable because the encryption keys will be rotated frequently. As I understand it, the weakness in CTR mode occurs when the same nonce AND key are used to encrypt. If the key is rotated, say, every 2 months, it's unlikely that there would ever be a nonce collision. 

This is a heterodox use of CTR mode - feel free to savage my idea if it is flawed. Thanks for your help.
A 6-byte nonce can expect to receive a collision 0.01% of the time after around 240,000 nonce generations (based on a birthday attack). After 100 such rotations (a little under 17 years, based on your 2-month rotation policy), that comes out to a likelihood of just under 1% of experiencing a collision. On the surface, to me that seems like a reasonable margin of security.

If practical, you may also want to consider simply using an autoincrementing counter for your IV. Allow the first byte to be a machine identifier, and then use a mutex to synchronize access to the remaining five bytes. Whenever you need an IV, lock the mutex, read the current value as the IV, increment it by one, save it, and release the mutex. This allows you to encrypt over one trillion messages with a single key before the nonce rolls over, and has zero possibility of collision as long as you detect IV wraparound.