The meaning of deep-rooted is firmly fixed/held, i.e. indeed berakar umbi, as given by PRPM.

So technically, the correct translation is sejarah yang sudah berakar umbi [lama is redundant and not necessary here].

However sudah berakar umbi is more suitable when speaking of ideas or principles.

With something like history, perhaps it is more appropriate to translate it as established, thus yang sudah bertapak/mapan or something similar.