Britain has threatened countries that ban homosexuality with losing aid payments unless they reform, David Cameron has said.
But he conceded that "deep prejudices" in some countries meant the problem would persist for years.
The prime minister said he had raised the issue with leaders of some of the states involved when he attended the Commonwealth heads of government meeting in Australia.
Britain was "putting the pressure on", he said. But it was not a problem that would be solved by the time Commonwealth leaders are next due to meet, in Sri Lanka in 2013.
Cameron warned Sri Lanka to improve its human rights record or face boycotts of the 2013 summit. He declined to discuss whether the UK could stay away but said he shared a "similar view" to that of the Canadian prime minister, Stephen Harper, who has said he will not attend.
Ending bans on homosexuality was one of the recommendations of a highly critical internal report on the future relevance of the Commonwealth, written by experts from across the member nations.
"We are not just talking about it. We are also saying that British aid should have more strings attached," Cameron said on BBC1's Andrew Marr Show in an interview recorded at the summit in Perth.
"This is an issue where we are pushing for movement, we are prepared to put some money behind what we believe. But I'm afraid that you can't expect countries to change overnight.
"Britain is one of the premier aid givers in the world. We want to see countries that receive our aid adhering to proper human rights. We are saying that is one of the things that determines our aid policy, and there have been particularly bad examples where we have taken action."
Cameron said he had spoken with a number of African countries and that more pressure had been applied by the foreign secretary, William Hague, who deputised for him during parts of the summit.
Asked about the prospects for the 2013 summit, Cameron said: "I think we will have moved on this but I don't suspect that in two years' time this issue will be solved. We are dealing with deep prejudices in some places."
Asked directly if he would stay away from the 2013 summit, Cameron said: "I don't want to get into all this. The message I have given is: the Tamil Tigers have been defeated, you're in government, you have an opportunity to show magnanimity and also to show a process of reconciliation and demonstrate to the rest of the world that you don't have things to hide. It is very important that pressure is applied.
"I think they should be aware of the fact that they are holding this Commonwealth summit in 2013 and it is up to them to show further progress so they can welcome the maximum number of countries."
Cameron also announced plans to deploy armed guards on British ships to protect them from pirates.
Under the plans, the home secretary will be given the power to license vessels to carry armed security, including automatic weapons, currently prohibited under firearms laws.
The prime minister said radical action was required because the increasing ability of sea-borne Somali criminals to hijack and ransom ships had become "a complete stain on our world".
Asked if he was comfortable with giving private security operatives the right to "shoot to kill" if necessary, Mr Cameron said: "We have to make choices. Frankly the extent of the hijack and ransom of ships round the Horn of Africa is a complete stain on our world.
"The fact that a bunch of pirates in Somalia are managing to hold to ransom the rest of the world and our trading system is a complete insult and the rest of the world needs to come together with much more vigour.
"I want to help lead this process and as part of that we are going to be taking the step of putting armed guards on our ships."
