Multi-key fully homomorphic encryption (MK-FHE) enables secure computation over ciphertexts under different keys, but its practicality is hindered by inefficient bootstrapping. In this work, we propose \(\textsf{HERDS}\) , a new MK-FHE scheme with highly efficient bootstrapping. Our bootstrapping framework improves upon the best-known complexity, reducing it from O(dkn) to O(kn), and further to \({O}(\sqrt{kn})\) under parallelization, where d is the gadget length (typically scaling with the number of parties k) and n is the LWE dimension. The framework consists of two main components: (i) a ciphertext conversion algorithm that transforms a multi-key LWE ciphertext into k vectorized RLWE ciphertexts via k optimized blind rotations and dk key-switching operations, and (ii) a hybrid accumulator that aggregates these into a single multi-key RLWE ciphertext. We implemented \(\textsf{HERDS}\) on both CPU and GPU platforms to demonstrate its practicality. For \(k=16\) , we achieve \(3.3\times \) and \(7.2\times \) improvements on CPU, compared to the state-of-the-art schemes by Kwak et al. (PKC 2024) and by Xiang et al. (ASIACRYPT 2024), respectively. We further achieve a \(195\times \) GPU acceleration, compared to our CPU runtime. As a byproduct, we design a new distributed-decryption protocol, which allows us to obtain a ciphertext with a small noise bound, and thus does not blow up the parameters.