Guarda, io penso che il problema sia nel calcolo dell'hash, e non nella trasformazione da array di byte in stringa.

Anche perchè l'md5 sono 32 caratteri (o meglio, 32 byte) quindi la trasformazione da array di byte (che cmq sarà lungo sempre 32) in stringa è un operazione a tempo costante.

edit: ho visto solo ora i codici che hai postato, quel codice che ti ho postato l'hai usato per trasformare il prodotto del metodo "veloce"? (quello che sta nel link per intenderci)

Perchè il codice riportato direttamente nel tuo messaggio non mi sembra molto adatto per fare hash da files