EDIT: after further investigation this is actually mistaken and doesn't affect the majority of store operations; this one is likely not the issue
Quick #nix PSA: do you run a binary cache? Is WantMassQuery: 1 not in its nix-cache-info file?
~~If it's not in there, clients will take an extremely long time to query whether paths are present in your cache by trying them one by one serially.~~