Generally, you pay a percentage of your monthly payment for every month you have left.
Depending on who you're with there's a maximum you pay... I'm fairly certain Telus said they were a max of $200 when I was looking into it, THINK Roger's is a max of $180.
What kinda phone did you have that they lost? Did you pay for it originally or was it part of a package? I'd tell them, they lost your phone, instead of making them pay for a new one, you'll just walk away from the contract, which will save tem money in the long run anyway.
Good luck