Human networks of sexual contacts are dynamic by nature, with partnerships forming and breaking continuously over time. Sexual behaviours are also highly heterogeneous, so that the number of partners reported by individuals over a given period of time is typically distributed as a power-law. Both the dynamism and heterogeneity of sexual partnerships are likely to have an effect in the patterns of spread of sexually transmitted diseases. To represent these two fundamental properties of sexual networks, we developed a stochastic process of dynamic partnership formation and dissolution, which results in power-law numbers of partners over time. Model parameters can be set to produce realistic conditions in terms of the exponent of the power-law distribution, of the number of individuals without relationships and of the average duration of relationships. Using an outbreak of antibiotic resistant gonorrhoea amongst men have sex with men as a case study, we show that our realistic dynamic network exhibits different properties compared to the frequently used static networks or homogeneous mixing models. We also consider an approximation to our dynamic network model in terms of a much simpler branching process. We estimate the parameters of the generation time distribution and offspring distribution which can be used for example in the context of outbreak reconstruction based on genomic data. Finally, we investigate the impact of a range of interventions against gonorrhoea, including increased condom use, more frequent screening and immunisation, concluding that the latter shows great promise to reduce the burden of gonorrhoea, even if the vaccine was only partially effective or applied to only a random subset of the population.