One way that's I guess is likely to be slower but more robust regarding the label index [0] in @jylls's answer is to call the legend() function again.

import numpy as np
import matplotlib.pyplot as plt
import matplotlib.animation as animation

fig,ax = plt.subplots()
dt = 0.01
N_frames=30
x=np.random.choice(100,size=N_frames,) #Create random trajectory
y=np.random.choice(100,size=N_frames,) #Create random trajectory
graph, = plt.plot([], [], color="gold",lw=5,markersize=3,label='Time: 0')
L=plt.legend(loc=1) #Define legend objects

def init():
    ax.set_xlim(0, 100)
    ax.set_ylim(0, 100)
    return graph,

def animate(i):
    lab = 'Time:'+str(round(dt+dt*i,2))
    graph.set_data(x[:i], y[:i])
    graph.set_label(lab) #Update label each at frame
    ax.legend(loc=1)

    return graph,

ani = animation.FuncAnimation(fig,animate,frames=np.arange(N_frames),init_func=init,interval=200)
plt.show()