Assume an average winter temperature of, say, 9°C and that you want your house at at average of 19°C that's 3.5 kW average for 10°C of heating. For the coldest weather (-10°C) you need more like 30°C of heating, which takes you to 10.5kW. So, maybe 12kW would be okay but, that doesn't leave much margin for error. It's also big step down in size from your current boiler. In your position, I'd want at least 15kW and probably 18kW just in case, which is the compromise others have already suggested.
Don't forget that if you have a terraced house, if your neighbours decide to leave it unoccupied in the winter for some reason your gas consumption will rise with the increased losses through the party wall. So you need a bit in reserve in case this happens.