The Midrash (Bereishis Raba 61:3) and Yerushalmi (Chagigah 3:1) list him as one of the Talmidim of Rebbi Akiva, a contemporary of Rebbi Yehudah and Rebbi Meir (as it would seem from our Gemara as well). This is clear from Yevamos 93a as well, which puts him as a Rebbi of Rebbi Meir and Talmid of Rebbi Akiva.

We do find that Ben Azai found a scroll in Yerushalayim saying that REB"Y's Mishnayos are Kav v'Naki (Yevamos 49a), and Ben Azai himself was a younger contemporary of Rebbi Akiva. This would make it seem that REB"Y was somewhat older. However, it is possible that he was from the older students of Rebbi Akiva, and was well known even before he began to learn from Rebbi Akiva.

In Yoma 16a we learn that he is the author of Mishnayos Midos, which describes the Mikdash. In Midos he tells us that his uncle served as a Shomer in the Mikdash. Some derive from this that he was much earlier, and saw the Beis ha'Mikdash. The RAMA in a footnote in Sefer ha'Yuchasin (cited by Seder ha'Doros) also writes that there was an early REB"Y, meaning that there really were two REB"Y's (see Rav Halpern's Atlas Etz Chayim, for example). However there does not seem to be basis for this in the Rishonim and Acharonim, nor does there seem to be enough evidence for this in Shas. The Gemara always assumes the Halachah is like REB"Y because Mishnaso Kav v'Naki and never tries to distinguish between which REB"Y is being quoted. (Seder ha'Doros only has a single REB"Y, and refutes Rama's claim.)

Best wishes,

Mordecai Kornfeld