Online Social Networks (OSNs) are the core of many social interactions nowadays. Privacy is an important building block of free societies, and thus, for OSNs. Therefore, OSNs should support privacy-enabled communication between citizens that participate. OSNs function as group communication systems and can be build in centralized and distributed styles. Centralized, privacy is under the sole control of a single entity. If this entity is distributed, privacy can be improved as all participants contribute to privacy. Peer-to-peer-based group communication systems overcome this issue, at the cost of large messaging overhead. The message overhead is mainly caused by early message duplication due to disjunct routing paths. In this paper, we introduce ant colony optimization to reduce the messaging overhead in peer-to-peer-based group communication systems, bridging the gap between privacy and efficiency. To optimize disjunct routing paths, we apply our adapted privacy sensitive ant colony optimization to encourage re-usage and aggregation of known paths. Our results indicate a 9-31% lower messaging overhead compared to the state of the art. Moreover, our ant colony optimization-based method reuses paths without leaking additional information, that is, we maintain the anonymity sets so that participants remain probable innocent.