The selection of red, passive galaxies in the early Universe is very challenging, especially beyond z~3, and it is crucial to constrain theoretical modelling of the processes responsible for their rapid assembly and abrupt shut-down of the star formation. We present here the analysis of ALMA archival observations of 26 out of the 30 galaxies in the deep CANDELS GOODS-South field that we identified as passive at z~3-5 by means of a careful and conservative SED fitting analysis. ALMA data are used to verify the potential contamination from red, dusty but star--forming sources that could enter the sample due to similar optical--nearIR colours. With the exception of a few marginal detections at <3sigma, we could only infer upper limits, both on individual sources and on the stacks. We translated the ALMA continuum measurements into corresponding SFRs, using a variety of far-IR models. These SFRs are compared with those predicted by secondary star-forming solutions of the optical fits and with the expected position of the star formation Main Sequence. This analysis confirms the passive nature of 9 candidates with high confidence and suggests that the classification is correct for at least half of the sample in a statistical sense. For the remaining sources the analysis remain inconclusive because available ALMA data is not deep enough, although the stacking results corroborate their passive nature. Despite the uncertainties, this work provides decisive support to the existence of passive galaxies beyond z~3.