I've heavily used probably four Linux package managers, plus both major ones on Mac, and have used two or three less-common Linux package managers at least a little bit, plus a couple of the BSDs. Oh, and Chocolatey on Windows.
I've never gotten this complaint about Brew at all. It has never seemed notably slow to me.