I was involved in the conversations about this topic on the Polymath4 blog (actually, looking back, it looks like I was the one who dug up that old paper...) and I came to believe that there was no such algorithm (randomized, conditional, whatever). Certainly I searched the literature as best I could and didn't find one. But I'm pessimistic about finding a reduction from factoring, for reasons I touched on in the linked post.

I was going to mention this beautiful argument, but actually I don't think it applies here -- you can only use squarefreeness to tell if a prime factor $p | N$ ramifies over some extension (Edit: I *think* this is true -- but something weird might happen if the extension isn't Galois? Maybe? I know so little algebraic number theory it's not even funny), but that's only possible if p divides the discriminant -- but you can do that already by the Euclidean algorithm. So squarefreeness would only let you maybe factor if for some reason you could do the algorithm quickly in number fields with huge discriminant, which admittedly might be possible. Edit: Although of course if the discriminant is big enough to make a difference, it's unclear how you'd extract information about p anyway. Which, modulo a whole bunch of holes and handwaving, would seem to rule out any naive attempt to adapt that "reduction."