The main reason for this is that the database is overloaded. When you configure Audit Trail on Azure, the database that stores the changes is set up with an average value for throughput.
The metric Microsoft use is RU per second or RU/s. RU stands for 'Request Units'. By default, the database is set up as having a capacity of 1000 request units per second. If there are too many requests to the database, as can happen when there is a large number of changes or when the database grows considerably, then the throughput may be throttled i.e. processing and searching will slow down.
You can see this on the Azure portal dashboard as shown below:
Above we can see that the value for Highest RU Consuming Shard is always 100%. This means that the database is working at capacity.
We can change this value so that the RU/s is larger or simply allowed to grow as needed. Note, however, the larger the value the greater the cost.
On the screen above you can adjust the maximum value for RU/s to cope with a larger throughput.