Unpredictable sequence numbers

I would suggest to do some benchmarking/profiling first. It seems very unlikely to me that the difference between md4 and md5 of only a few bytes calculated only once at the beginning of a connection would have a measurable impact.

Much less be a bottleneck.

But estimating performance is very hard so measure first the difference between the two algorithms.