Я думаю, вы, если добавите месяцы и дни отдельно, должны возникнуть проблемы с последними днями месяцев, например, если дней 30, если не удалось в феврале.
Поэтому я предлагаю добавлять только дни, например:
df['Time'] = (pd.to_datetime(df.Time, format='%Y') +
pd.to_timedelta(np.random.randint(365, size=len(df)), unit='d'))
print (df)
Time
0 1995-06-02
1 1996-01-02
2 1997-05-06
3 1998-12-20
4 1999-11-22