Yet even at 46, the tall centre-back has not hung up his boots, has not put on a single extra gram and still plays for his home village of Kozusany. He devotes himself to his family, investments and charity.
Rozehnal looks very happy, if only that knee would stop making itself known. In a major interview with Flashscore, he speaks in his typically calm voice about Czech football, his time in Paris, and playing with Eden Hazard at Lille.
The Czech under-20 national team recently beat Switzerland 5-2 at a tournament in Portugal, lost 0-2 to Poland and 0-5 to Portugal. What did the matches tell you?
"That we are competitive. If the team gives 100%, stays focused and does what coach Jilek asks of them, we can stand up to better opponents in Europe. We played worse against Switzerland than against Poland, but we lost.
"Portugal's quality was obvious; the boys did not give everything they had. Some of our players are already playing league football, but the Portuguese were on another level. That is more a question for the club coaches. We can smooth things out with the national team, motivate them and bring out the best in them, but the main work lies with the players and the clubs."
You have been with this age group since the under-16s. Are you part of the coaching staff?
"I would not want to describe myself as an assistant, even though the boys address me that way. At the first camp, they dared to call me Rozi, and I am fine with that during training, but otherwise they still use the formal address. The excessive respect has gone. They see me as part of the team. I support them.
"I want them to take confidence, perspective and experience from me. We chat on the massage tables and they ask me what it is like abroad. Where was it best, where was it worst? Football is harder than it used to be. More demanding and more physical.
"But they also have resources for improvement that we did not have. During training I mostly watch the defensive phase, and during matches I sit in the stand with the analyst. At half-time we pass information down to the bench."
Did being in Portugal bring back memories of EURO 2004, when you won bronze?
"Even though we played in a different stadium, of course it did. They are good memories. It was my first major tournament. Before it, the newspapers debated what chance I had of making the squad. It was not a very big one."
And you even played in the epic match against the Netherlands.
"Surprisingly, I got on and even had a chance. Although I was not in the starting 11, I was part of a fantastic team and learned from the best. An invaluable experience."
Does the semi-final against Greece still hurt?
"It still hurts. It should have been at least a final. Under coach Bruckner, we played attractive, constructive and pressing football. If we had got through that one match, we might have gone on to win the title."
That was an exceptional generation of Czech football: Cech, Ujfalusi, Jankulovski, Poborsky, Rosicky, Smicer, Baros, Koller... every name a personality. Will top players emerge again?
"To be completely honest, we are still behind, but I see potential. Some were ahead of the pack at 16, but they are no longer in the national team, which is a natural progression. If we handle it properly, follow the European path and do not do everything our own way just because we think we know best, things could improve.
"We do not know best. There are better coaches in the world. I do not mean to offend anyone, but we should learn from them."
Should there be a unified methodology?
"Yes, but we also run into opinions at the clubs: What are those other people going to teach us? We do it best, after all."
You won a title (in Belgium) and then moved to PSG...
"Dortmund was also discussed a lot at the time, but it ended up being PSG and I was happy. Suddenly I was at the Parc des Princes. Another level again. From a footballing perspective, I liked Paris the most. Apart from one match I missed through suspension, I played everything. I felt indestructible.
"I arrived in Germany for the World Cup having played 60 matches that season. I felt great thanks to the coaches and the fans in Paris, who accepted me. In my second season I played as a central midfielder, which was great. I have only the best memories."
Was that your first impression too?
"Yes. Brugge pushed me to a higher level of training intensity. After my first training session in Belgium, I was on an IV drip, and it was not even a fitness session. The intensity was incredible! We trained hard in Olomouc, especially under the old-school coaches Ulicny and Kalvoda, but in Brugge the players' aggression in training was on another level.
"I had three pitbulls in every position. In Paris, everyone was an international: Sylvain Armand, Pedro Pauleta, Vikash Dhorasoo and Jerome Rothen. I had Mario Yepes, the Colombian stalwart, alongside me in defence. We clicked and played together."
What was the atmosphere around PSG among the fans and within the club before the Qatari owners arrived?
"It was a different Paris. Calmer than it is now with the new owner. Paris and Marseille were the biggest teams, Le Classique and huge matches. Back then, there were two stands at the Parc des Princes shouting over each other. An incredible atmosphere. The people around the club were pleasant."
There is a famous story about you first parking your old Golf outside the Parc des Princes next to Rothen's Ferrari.
"It was funny. The people at the gate were tapping their heads, wondering who I was. Maybe they did not even want to let me in."
You are an authentic person; you do not need to pretend. Not everyone can manage that in the football bubble.
"Jerome Rothen was a footballer through and through. He now hosts a podcast and really goes for it. He had an excellent left foot. He played brilliantly and enjoyed everything that came with it, and still does. But he is a good person; he could also talk to you normally.
"Most of the boys in the PSG dressing room were very friendly. Pedro Pauleta told me in the sauna about a certain Cristiano Ronaldo, who was just starting out with the national team."
What did he say? That he would be good?
"This guy is going to be good! I realised that at Newcastle, when Ronaldo sped past me for United like he was on a motorbike. I remembered that Pedro had not been talking nonsense. Ronaldo became one of the biggest figures in world football."
In your second season at PSG, you were fighting relegation and finished only 15th. What went wrong?
"I do not think anything went wrong; the results simply did not come. A new coach, Guy Lacombe, arrived and started playing me in midfield. I was surprised, but happy about it. I saw a lot of the ball and enjoyed my football despite the poor results.
"We only secured our survival four matches before the end, which had never happened there. The stress was immense."
And you were named PSG's player of the season.
"I did not know that. I never received such a trophy, so I would like to claim it. I went on holiday and then never returned there, which I regretted. I had good relationships there and felt comfortable, but I left for Newcastle. Maybe I will go and collect that trophy one day!"
You struggled at Newcastle, while PSG grew under its new owner. Did you regret it?
"I regretted leaving a good team with great fans, where I had shown what I could do, to go to Newcastle, which everyone around me said was the best choice, but I did not feel it. Petka, my wife, taught me that your first thought, your intuition, is important."
What do you make of the current PSG under Luis Enrique?
"I like it a lot. I want to visit their modern training centre and facilities. The kit man, Nacerdine Sekai, whom everyone calls Didi, is still the same. A wonderful person. I saw him celebrating their Champions League victory.
"When the new owners were taking over, we were beating them with Lille. And they already had Cavani, Ibrahimovic and Lavezzi, top stars. And we won the double with Lille. Nothing happens overnight. Two years later, they started winning everything. I still follow PSG; it has a special place in my heart. Enrique has brought order to the team and polished it further. Beautiful football."
What made Lille special?
"The family atmosphere among everyone at the club, including the team. At Lille too, we had internationals in every position."
And a certain Eden Hazard...
"He was just coming to the fore. And Gervinho too. The team spirit was fantastic; we kept turning results around. We were on a roll. We won the title three or four matches before the end."
Did you tell anyone in the sauna that Hazard would become one of the best players on the planet?
"It was obvious after his first year, and he polished his game even further after that. Great mentality, normal person. He never acted like a star. You would not have guessed he was a superstar of the French league. He was a bit of a slacker in training, though, and I am telling him that. I like him very much. A game-changer."
You played five seasons at Lille, longer than at any other club.
"They valued me even as a substitute. I already had a few years behind me, my family had settled there and we liked it. We had lots of friends, and when there was an opportunity to extend my contract, I did. I always played 20 matches a season, or 25 with the cup competitions."
What advice would you give young footballers as a player who won six trophies in European leagues?
"They have to realise whether they love football or not. And that does not apply only to football; it applies to anyone. You know perfectly well that you have to work your way up. It will not simply fall into your lap. The most important thing is to be good people. I would not be sitting here with you if I did not see you as a good person."