So i need to call Serial.flush() after every Serial.write() right?
Maybe. Maybe not. You need to call Serial.flush() after the last Serial.write() for the packet. If the whole packet is written in one step, then yes. Otherwise, no.
It dramatically increased the frame sending time but it's more consistent for sure.
Sure, because you now ensure that Elvis has left the building before continuing.
Is there any other way to decrease the sending time but to provide its consistency at the same time?
Aside from the obvious (pick up the speed, send less data)? No.