I think an awful lot depends on the exact circumstances, the condition of the ground, and the experience level of the officers and NCOs. Is more information available?
The first thing catching my eye is, "The brigade was understaffed". Yes, 900 men take less time to move than 5,000 - IF the stripes and straps know what they're doing.
There was no "standard marching formation" -- that's why there are so many options in the manuals. If a narrow road is available, it's best to march by the flank ("column of fours"). If the road is wide enough it's better to form in column according to the largest subdivision (sections, platoons, companies, or divisions) that will fit. Really open ground is pretty uncommon on Civil War battlefields; there are always buildings, fences, woods, ponds etc. that complicate things if you make the formation too wide too soon.
A column at "full distance" takes up the same length as marching by the flank, but requires much more width; so it's often a stupid formation. Better to put your men in close column (unless you are vulnerable to artillery fire) since you can really stack up a lot of guys in minimum space. And a close column can be deployed on any subdivision, either left or right, taking a lot less time than a diagonal move like "Forward into Line".
So, if the officers know the ground and can choreograph all this in advance, it can be done very quickly. If they've just marched 20 miles and don't even know what county they're in -- different story.
Finally, brigades don't form continuous lines like battalions - at least not per the manuals. There are supposed to be gaps, which allow units to maneuver without running into each other, passage of skirmishers, etc. Somebody has to set the basis and direction of the brigade line, and after the battalions deploy they have to be dressed on it - unless it's a case of "y'all get on that fence thar and give 'em a volley". That takes more time.
So my vote is between five and twenty minutes.