Have you bothered to work out the math for this?
at 115,200 baud, each bit is about 9 uS
A byte is 72 uS
A 4 byte int is 288 uS
Even if you usually send less than the full 4 bytes worth, it looks like there is no way to send all your data in less than a millsecond.
(I did not even include start bits!)
It might be a bit faster to send the data as hex bytes to cut down the conversion time, but that is probably not your problem.