A Majorana-based qubit can form within the fermion parity subspace of a two-island topological superconductor setup consisting of four Majorana zero modes. We study the relaxation time of this Majorana qubit induced by the intrinsic Majorana-phonon interaction in combination with single-electron tunneling between the two islands. The theory is developed for both the spinless p-wave Kitaev chain model and the spin-orbit-coupled semiconductor nanowire with induced superconductivity and Zeeman splitting. We systematically discuss the dependence of the relaxation rate on Majorana charge distribution (varying with the chemical potential, magnetic field, superconducting pairing, spin-orbit coupling, and island length) as well as on phonon wavelength and the length of the tunnel barrier. Importantly, the accompanied phonon energy can be tuned by the voltage bias over the tunnel barrier, leading to relatively easy manipulation and suppression of the relaxation rate.