Authentication shouldn’t take more than 4 or 5 bytes, and only in the messages you actually want to authenticate.
A simple scheme might be:
Round the current wall clock time downward 5 minutes, use that as the key for a keyed hash of your message.
When you get a message, validate the hash, accepting a match for either the current or previous 5 minutes window.
This way no message can be replayed after about 5 to 10 minutes max depending on clock accuracy, which is already a lot better than nothing.
As I understand it, the birthday paradox doesn’t really apply to MACs, so with a 4 byte MAC you literally have to try 2 billion times before you get a hit, but each try takes possibly several seconds, so it would take 5 years of 10 packets a second to have 50% chance of your fake packet getting through, and a 5 byte MAC would take hundreds of years.
If you need even more security, store a buffer of every single message hash for all authenticated messages, don’t accept a message with an ID we have seen within the last 20 minutes. That gives replay attack protection even within the window, and would only require a tiny ring buffer because the max packet rate is so low.
For devices with no time source, you could get the time fairly securely:
At an interval of N hours, if you have not seen someone send a time update broadcast on each of your channels, send the current time with authentication.
If you have not received the current time in the last month or since bootup, fall back to allowing unencrypted messages so someone can fix that.
The interval N is determined by your time source, as in NTP tiers, GPS>NTP>Bluetooth to Phone>Admin Channel>Other Channel.
So for every channel, only one node is going to be broadcasting the time a few times a day, and it’s going to be whichever node is the best, and if nobody has a GPS or NTP, you will still be able to sync for a week or two because someone will start sending their local clock time.
This time scheme would have other uses too besides encryption, because securely getting the time is a pretty common requirement.