A search for events with a dark photon produced in association with a dark Higgs boson via rare decays of the Standard Model $Z$ boson is presented, using 139 fb$^{-1}$ of $\sqrt{s} = 13$ TeV proton-proton collision data recorded by the ATLAS detector at the Large Hadron Collider. The dark Higgs boson decays into a pair of dark photons, and at least two of the three dark photons must each decay into a pair of electrons or muons, resulting in at least two same-flavor opposite-charge lepton pairs in the final state. The data are found to be consistent with the background prediction, and upper limits are set on the dark photon's coupling to the dark Higgs boson times the kinetic mixing between the Standard Model photon and the dark photon, $\alpha_{D}\varepsilon^2$, in the dark photon mass range of $[5, 40]$ GeV except for the $\Upsilon$ mass window $[8.8, 11.1]$ GeV. This search explores new parameter space not previously excluded by other experiments.