Recently put a bit of thought into this. When a decision was made in Rome, or a report of a battle was to be sent back at around 230 BC - 150 AD, how did the messages get sent? Also, how long would it take for a message to arrive from the edges of the empire to Rome or vice versa?
Weeks.
The Persians had a lovely system of post-riders, who could change horses and change messengers, over improved brick roads, often, and get from the Mediterranean to Susa in a matter of days. (Herodotos, Xenophon)
The Romans, in the pagan empire would put one guy on one horse & this messenger and horse would carry the dispatch pouch from Britain to Rome.
Mail between Egypt & Rome might make it in a week if the seasonal winds were with you. Otherwise it was weeks of adverse winds. (Lionel Casson, Travel in the Ancient World which specifically covers sending messages.)
Later laws of Justinian regulate the weight to be carried by post-riders, so things did improve. But in your time - pretty slow. Your fastest bet is often a galley.