ALMA observations have somewhat surprisingly revealed the presence of large amounts of dust in the first generations of galaxies in the Universe. Unfortunately, their dust temperature Td remains difficult to determine due to the limited available FIR continuum data at redshift z>5. This introduces large uncertainties in several properties of high-z galaxies, namely their dust masses, infrared luminosities, and obscured fraction of Star Formation Rates (SFR). We have developed a new analytical method to constrain Td using a single continuum data point at 158 microns by combining it with the overlying CII emission. With our method, one can analyse uniquely the large number of [CII] and continuum detections at high-z provided by recent ALMA Large Programs such as REBELS and ALPINE. REBELS sources analysis allows us to extend for the first time the previously reported Td-redshift relation into the Epoch of Reionization (EoR). We find that Td increases with redshift, but more mildly than previous suggestions based on stacked SEDs fitting at z<4. We produce a new physical model that explains the increasing Td(z) trend with the decrease of gas depletion time, tdep=Mg/SFR, induced by the higher cosmological accretion rates at early times. The model also accounts for the observed Td scatter at a fixed redshift. A dust temperature increase at high-z has testable and potentially relevant implications: (a) it alleviates the problem of the uncomfortably large dust masses deduced from observations of some EoR galaxies, (b) it results in a larger obscured fraction of the SFR.