We present a strategy to alleviate the sign problem in continuous-time quantum Monte Carlo (CTQMC) simulations of the dynamical-mean-field-theory (DMFT) equations for the spin-orbit-coupled multiorbital Hubbard model. We first identify the combinations of rotationally invariant Hund coupling terms present in the relativistic basis which lead to a severe sign problem. Exploiting the fact that the average sign in CTQMC depends on the choice of single-particle basis, we propose a bonding-antibonding basis $V_{j3/2mathrm{BA}}$ which shows an improved average sign compared to the widely used relativistic basis for most parameter sets investigated. We then generalize this procedure by introducing a stochastic optimization algorithm that exploits the space of single-particle bases and show that $V_{j3/2mathrm{BA}}$ is very close to optimal within the parameter space investigated. Our findings enable more efficient DMFT simulations of materials with strong spin-orbit coupling.