Magha Vadya (Krishna) 13 is celebrated as Maha-Shiva-Ratra (Longest auspicious night of the year).
While in antiquity this day of Magha Vadya (Krishna) 13 fell on the day of Winter solstice (and thus longest night), in our times the day falls sometime in January-February-March timeframe and thus no longer aligns with the longest night of the year (21/22 December).
One can easily calculate the time, in antiquity, when Magha Vadya (Krishna) 13 coincided with that of Winter Solstice.
Keep in mind, that lunar tithi would move by 10-11 days with respect to a day on Julian/Gregorian calendar in the short term, until a correction of Adhika masa is applied.
What does it means in lay term is that Magha Krishna 13 will not coincide with the day of winter solstice, each year in a consecutive fashion and thus one must talk in the terms of ‘MIDDLE POINT’ or ‘MEDIAN POINT’ of Magha Krishna 13 coinciding with the day of Winter solstice.
We can easily estimate this time to be that of 3000 BCE. For example on 12 January 3002 BCE, the day of Magha Krishna 13 coincided with the day of Winter Solstice. This day was then would have been celebrated as day (or rather the night) of MahaShivaRatra.
Since we can only talk in terms of specific tithi (Magha Krishna 13) as ‘MIDDLE POINT’, we have to define the beginning of the tradition of MahaShivaratra as a time interval, as opposed to a specific year.
Taking a time interval of 15 days on both sides of this ‘MIDDLE POINT’, we can assert that the tradition of MahaShivaRatra began sometime during (3000 BCE +/_ 1000 years), i.e. sometime during 4000 BCE – 2000 BCE), i.e. about 6000 to 4000 years ago.
(The range of 1000 years is due to the time it takes for ‘MIDDLE POINT’ (of Tithi) to move by ~15 days on each side. It takes about 72 years for the ‘MIDDLE POINT’ to move by ONE tithi, and thus 72 x 15 = 1080~ 1000 years.)