The weak link in reproducibility is that you currently have no trivial way of recreating the same random order of the linked object files.
Currently the random relinking is implemented literally through a call to "| sort -R" (-R for random order) on the list of object files, passed as arguments to the linker. I suppose if sort -R took a seed argument that was saved somewhere safe (chmod 400), the linking order can still be reproduced, and the resulting executable checksummed against the state of the system.
Yet another solution is to re-sort the executable into a stable order and compare the hash of that.