Randomizing the Auto Increment in Mysql

We have a database, where we insert data into table whenever we receive an order from our services. We use auto_increment to generate the ID and assign the order with the same. This is usually same everywhere. But the problem is, since this information is passed to third party vendors, they are able to trace, how many orders we are receiving per day. By sending a request in the early morning and sending another request in midnight and count the difference in the ID. This is giving insight information of our services. Since it's bit complex system, we can't do complex operation that can randomise this. My initial idea is to generate auto_increment numbers in bit random fashion way. 1,2,3,4,5,67,68,69,70,71,133,134,135,136,137,189,190,191,192,193,194 I guess it should be simple, as Mysql runs out of cache, generate next sequence by appending some random number. How to achieve this without impacting the performance?